hdu5568 sequence2（dp+大数）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5568

题目大意：

给一段长度为n的序列，现在在其中取k个，问这k个是递增的取法有多少种。

范围：n<=100。

思路：

可以用dp来解决，跟前面做过的一题一样。

设f[i][j]，代表在前i个里面选了长度为j并且以a[i]为结尾的取法，那么就有转移方程：f[i][j]=Σf[k][j-1]（a[k]<a[i]）。

时间复杂度O（n^3）。

但是考虑极端情况，100个里面取50个的时候，很显然已经溢出了，所以这里用大数处理。字符串模拟一下即可。

代码：

#include<stdio.h>
#include<string.h>
#define ll __int64
 char f[105][105][505];
 int max(int a,int b)
 {
     return a>b?a:b;
 }
 void add(int x,int y,int z)
 {
     if(z<y-1)return;
     char s[500];
     int q=0,i,j,t=0,l1,l2;
     l1=l2=0;
     for(i=0;i<500;i++)
        s[i]=0;
        for(i=499;i>=0;i--)
        {
            if(t==0&&f[x][y][i]==0)continue;
            else if(t==0&&f[x][y][i]){l1++;t=1;}
            else {l1++;}
        }
        t=0;
        for(i=499;i>=0;i--)
        {
            if(t==0&&f[z][y-1][i]==0)continue;
            else if(t==0&&f[z][y-1][i]){l2++;t=1;}
            else l2++;
        }
        t=0;
        q=0;
    for(i=0,j=0;i<l1&&j<l2;i++,j++)
    {
        s[q]=s[q]+f[x][y][i]+f[z][y-1][j];
        if(s[q]>=10){
            s[q]-=10;
            s[q+1]++;

        }
        q++;
    }
    while(i<l1){
        s[q]=s[q]+f[x][y][i];
        if(s[q]>=10){
            s[q]-=10;
            s[q+1]++;
        }
        i++;
        q++;
    }
    while(j<l2){
        s[q]=s[q]+f[z][y-1][j];
        if(s[q]>=10){
            s[q]-=10;
            s[q+1]++;
        }
        j++;
        q++;
    }
    int flag=0,xx=0;
    for(i=499;i>=0;i--)
    {
        if(flag==0&&s[i]==0)continue;
        else if(flag==0&&s[i]){
            flag=1;
            f[x][y][i]=s[i];
        }
        else f[x][y][i]=s[i];
    }

 }
int main()
{
      int  n,k,b[105];
    while(scanf("%d%d",&n,&k)!=EOF){
        memset(f,sizeof(f));
        for(i=1;i<=n;i++)
            scanf("%d",&b[i]);
         for(i=1;i<=n;i++)
            f[i][1][0]=1;
         for(i=1;i<=n;i++)
            {for(j=2;j<=k;j++)
         {
             if(i<j)continue;
             for(int l=1;l<i;l++)
                if(b[l]<b[i])add(i,l);
         }
    }

        char s[500],sum[500];
        for(i=0;i<500;i++)
            {s[i]=sum[i]=0;}
         for(i=1;i<=n;i++)
            {
                if(i<k)continue;
                int q=0,w=0;
               for(j=499;j>=0;j--)
               {
                   if(q==0&&f[i][k][j]==0)continue;
                   else if(q==0&&f[i][k][j]){
                    s[w++]=f[i][k][j];q=1;

                   }
                   else {s[w++]=f[i][k][j];}
               }
               for(j=0;j<w;j++)
               {
                   int x=s[w-1-j]+sum[j];
                   if(x>=10){
                    sum[j]=x-10;
                    sum[j+1]++;
                   }
                   else sum[j]=x;
               }
            }
            int ff=0;
        for(i=499;i>=0;i--)
        {
            if(ff==0&&sum[i]==0)continue;
            else if(ff==0&&sum[i]>0){
                printf("%d",sum[i]);
                ff=1;
            }
            else printf("%d",sum[i]);
        }
        if(ff==0)printf("0");
         printf("n");
    }
    return 0;
}