hdu5568 sequence2（dp + 高精度） - dblank

# sequence2

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 385    Accepted Submission(s): 151

Problem Description

Given an integer array bi with a length of n, please tell me how many exactly different increasing subsequences.

P.S. A subsequence bai(1ik) is an increasing subsequence of sequence bi(1in) if and only if 1a1<a2<...<akn and ba1<ba2<...<bak.
Two sequences ai and bi is exactly different if and only if there exist at least one i and aibi.

Input

For each cases, first come 2 integers, n,k(1n100,1kn)

Then follows n integers ai(0ai109)

Output
For each cases, please output an integer in a line as the answer.

Sample Input
3 2 1 2 2 3 2 1 2 3

Sample Output
2 3

Source
BestCoder Round #63 (div.2)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<cstring>
using namespace std;
int a[110], dp[110][110][42];
int main()
{
int n, k;
while(cin>>n>>k)
{
for(int i = 1; i<=n; i++)
scanf("%d", &a[i]);
memset(dp, 0, sizeof(dp));
for(int i = 1; i<=n; i++)
dp[i][1][1] = 1;
for(int i = 1; i<=n; i++)
{
for(int j = 2; j<=k; j++)
for(int l = 1; l<i; l++)
if(a[i]>a[l])
{
int t = 0, w = 0;
for(int r = 1; r<=40; r++)
{
w = (dp[i][j][r] + dp[l][j-1][r] + t)/10;
dp[i][j][r] = (dp[i][j][r] + dp[l][j-1][r] + t)%10;
t = w;
}
}
}
int ans[42];
memset(ans, 0, sizeof(ans));
for(int i = 1; i<=n; i++)
{
int t = 0, w = 0;
for(int r = 1; r<=40; r++)
{
w = (dp[i][k][r] + ans[r] + t)/10;
ans[r] = (dp[i][k][r] + ans[r] + t)%10;
t = w;
}
}
int ok = 0;
for(int i = 40; i>=1; i--)
{
if(ans[i]||ok)
{
printf("%d", ans[i]);
ok = 1;
}
}
if(!ok) printf("0")
printf("\n");
}
return 0;
}