hdu5568 sequence2(dp + 高精度) - dblank

hdu5568 sequence2(dp + 高精度)

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

Several test cases(about 5)

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)
题意:给你一个数列,求里面长度为k的上升子序列有多少。高精度。
思路:dp[i][j]表示以第i个元素结尾的长度为j的上升子序列的长度,dp[i][j] = sum(dp[1~(i-1)][j-1])。
代码写的有点丑。。。
#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;  
}

 

相关文章

发表新评论