rnqoj-38-串的记数-dp+大整数加法

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
#include<iostream>  
using namespace std;  
int dp[61][61][61][101];  
void jia(int a,int b,int c,int x,int y,int z)  
{  
    int l1,l2,i,j;  
    l1=dp[a][b][c][0];  
    l2=dp[x][y][z][0];  
    if(l1==0)  
    {  
        for(i=0;i<=l2;i++)  
        {  
            dp[a][b][c][i]=dp[x][y][z][i];  
  
        }  
        return ;  
    }  
    if(l2==0)return ;  
    int ca,leap;  
    leap=0;  
    for(i=1,j=1;i<=l1&&j<=l2;i++,j++)  
    {  
        ca=dp[a][b][c][i]+dp[x][y][z][j]+leap;  
        dp[a][b][c][i]=ca%10;  
        leap=ca/10;  
    }  
    while(i<=l1)  
    {  
        ca=dp[a][b][c][i]+leap;  
        dp[a][b][c][i]=ca%10;  
        leap=ca/10;  
        i++;  
    }  
    while(j<=l2)  
    {  
        ca=dp[x][y][z][j]+leap;  
        dp[a][b][c][j]=ca%10;  
        leap=ca/10;  
        j++;  
    }  
    if(leap>0)  
    {  
        dp[a][b][c][max(i,j)]=leap;  
        i++,j++;  
    }  
    dp[a][b][c][0]=max(i,j)-1;  
}  
int main()  
{  
    int i,j,k,n;  
    dp[0][0][0][0]=1;  
    dp[0][0][0][1]=1;  
    for(i=0;i<=60;i++)  
    {  
        for(j=0;j<=i;j++)  
        {  
            for(k=0;k<=j;k++)  
            {  
                if(i>=1)jia(i,j,k,i-1,j,k);  
                if(j>=1)jia(i,j,k,i,j-1,k);  
                if(k>=1)jia(i,j,k,i,j,k-1);  
            }  
        }  
    }  
    while(~scanf("%d",&n))  
    {  
        for(i=dp[n][n][n][0];i>=1;i--)  
        {  
            cout<<dp[n][n][n][i];  
        }  
        cout<<endl;  
    }  
    return 0;  
}