10069 - Distinct Subsequences

[cpp]
描述：可惡的奇葩題，不但要求記憶化搜索，而且還要求高精度，大數據 10^100，真受不了，非得開了個大數才解決的，開小數還超時 
#include <cstdio>  
#include <cstring>  
#define N 100000000  
char str[10010],s[110]; 
int v[110][10010][13],len[110][10010]; 
int max(int x,int y) 
{ 
    return x>y?x:y; 
} 
int main() 
{ 
 //   freopen("a.txt","r",stdin);  
    memset(len,0,sizeof(len)); 
    int t,n,m,p,flag; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%s%s",str,s); 
        m=strlen(str); 
        n=strlen(s); 
        memset(v,0,sizeof(v)); 
        if(str[0]==s[0]) v[0][0][0]=1; 
        len[0][0]=1; 
        for(int i=1; i<m; i++) 
        { 
            flag=0; 
            len[0][i]=len[0][i-1]; 
            if(s[0]==str[i]) flag=1; 
            for(int k=0; k<len[0][i-1]; k++) 
            { 
                p=v[0][i-1][k]+flag; 
                v[0][i][k]=p%N; 
                flag=p/N; 
            } 
            if(flag) v[0][i][len[0][i]++]=flag; 
        } 
        for(int i=1; i<n; i++) 
            for(int j=i; j<m; j++) 
                if(s[i]==str[j]) 
                { 
                    flag=0; 
                    int count=max(len[i-1][j-1],len[i][j-1]); 
                    for(int k=0; k<count; k++) 
                    { 
                        p=v[i-1][j-1][k]+v[i][j-1][k]+flag; 
                        flag=p/N; 
                        v[i][j][k]=p%N; 
                    } 
                    len[i][j]=count; 
                    if(flag) v[i][j][len[i][j]++]=flag; 
                } 
                else 
                { 
                    for(int k=0; k<len[i][j-1]; k++) v[i][j][k]=v[i][j-1][k]; 
                    len[i][j]=len[i][j-1]; 
                } 
        flag=len[n-1][m-1]-1; 
        printf("%d",v[n-1][m-1][flag]); 
        for(int i=flag-1; i>=0; i--) 
        { 
            p=v[n-1][m-1][i]; 
            if(p>9999999) printf("%d",p); 
            else if(p>999999) printf("0%d",p); 
            else if(p>99999) printf("00%d",p); 
            else if(p>9999) printf("000%d",p); 
            else if(p>999) printf("0000%d",p); 
            else if(p>99) printf("00000%d",p); 
            else if(p>9) printf("000000%d",p); 
            else printf("0000000%d",p); 
        } 
        puts(""); 
    } 
    return 0; 
} 

描述：可惡的奇葩題，不但要求記憶化搜索，而且還要求高精度，大數據 10^100，真受不了，非得開了個大數才解決的，開小數還超時
#include <cstdio>
#include <cstring>
#define N 100000000
char str[10010],s[110];
int v[110][10010][13],len[110][10010];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
 //   freopen("a.txt","r",stdin);
    memset(len,0,sizeof(len));
    int t,n,m,p,flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",str,s);
        m=strlen(str);
        n=strlen(s);
        memset(v,0,sizeof(v));
        if(str[0]==s[0]) v[0][0][0]=1;
        len[0][0]=1;
        for(int i=1; i<m; i++)
        {
            flag=0;
            len[0][i]=len[0][i-1];
            if(s[0]==str[i]) flag=1;
            for(int k=0; k<len[0][i-1]; k++)
            {
                p=v[0][i-1][k]+flag;
                v[0][i][k]=p%N;
                flag=p/N;
            }
            if(flag) v[0][i][len[0][i]++]=flag;
        }
        for(int i=1; i<n; i++)
            for(int j=i; j<m; j++)
                if(s[i]==str[j])
                {
                    flag=0;
                    int count=max(len[i-1][j-1],len[i][j-1]);
                    for(int k=0; k<count; k++)
                    {
                        p=v[i-1][j-1][k]+v[i][j-1][k]+flag;
                        flag=p/N;
                        v[i][j][k]=p%N;
                    }
                    len[i][j]=count;
                    if(flag) v[i][j][len[i][j]++]=flag;
                }
                else
                {
                    for(int k=0; k<len[i][j-1]; k++) v[i][j][k]=v[i][j-1][k];
                    len[i][j]=len[i][j-1];
                }
        flag=len[n-1][m-1]-1;
        printf("%d",v[n-1][m-1][flag]);
        for(int i=flag-1; i>=0; i--)
        {
            p=v[n-1][m-1][i];
            if(p>9999999) printf("%d",p);
            else if(p>999999) printf("0%d",p);
            else if(p>99999) printf("00%d",p);
            else if(p>9999) printf("000%d",p);
            else if(p>999) printf("0000%d",p);
            else if(p>99) printf("00000%d",p);
            else if(p>9) printf("000000%d",p);
            else printf("0000000%d",p);
        }
        puts("");
    }
    return 0;
}