KIS---16级补考题--最长上升子序列变式---动态规划

Myth丶恋晨 2022-05-16 11:45 43阅读 0赞

Problem Description  
长度为 n 的一个序列，保证每个数都互不相同，问长度为 k 的上升子序列有多少个。

注：子序列是找出一个序列的一部分，不要求连续，比如 abcde 的序列，cde 和 ace 都是它的子序列。

Input  
输入数据有多组（数据组数不超过 100），到 EOF 结束。

对于每组数据：

第一行输入一个 n (0 < n <= 100)  
第二行输入 n 个整数 a\[i\] (0 < a\[i\] <= 1e9)  
第三行输入一个整数 k (0 < k <= n)  
Output  
对于每组数据，输出一行，表示长度为 k 的上升子序列有多少个，由于答案可能很大，你需要把答案对 1000000007 取模。

Sample Input  
5  
1 5 2 4 3  
2  
10  
1 2 3 4 5 6 7 8 10 9  
5  
Sample Output  
6  
196

#include<stdio.h>
    #include<stdlib.h>
    int jiecheng(int n)
    {
        int sum=1,i;
        for(i=2;i<=n;i++)
        {
            sum=i*sum;
        }
        return sum;
    }
    int main()
    {
        int n,k,i,j,c;
        int a[1000];
        int  b[1000];
        while(scanf("%d",&n)!=EOF)
        {
            for(i=1; i<=n; i++)
            {
                scanf("%d",&a[i]);
            }
            scanf("%d",&k);
            b[1]=1;
            for(i=2; i<=n; i++)
            {
                c=0;
                for(j=1; j<=i; j++)
                {
                    if(a[i]>a[j]&&c<b[j])
                        c=b[j];
                }
                b[i]=c+1;
            }
             int sum=0;
             for(i=1;i<=n;i++)
             {
                 if(b[i]==k)
                 {
                     sum++;
                 }
                 if(b[i]>k)
                 {
                     sum=(sum+jiecheng(b[i]-1)/(jiecheng(k-1)*jiecheng(b[i]-k)))%1000000007;
                 }
             }
            printf("%d\n",sum);
        }
        return 0;
    }

此题提交不正确，正在解决