题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1502

题目大意：找出总的满足条件的字符串数,num(a)=num(b)=num(c)且任何前缀均满足num(a)>=num(b)>=num(c)

解题思路：用dp[i][j][k]表示a取i个,b取j个,c取k个的状态下最多有多少种满足条件的情况,容易推得状态转移方程如下：

dp[i][j][k]=dp[i-1][j][k](i>j时)+dp[i][j-1][k](j>k时)+dp[i][j][k-1](k>0时)

根据该状态转移方程即可输出最后的结果dp[n][n][n]

因为本题的数据结果比较大，所以还需要用到高精度，对不会用java的人就只能手敲一个大数相加了。。。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #define scan(a) scanf("%d",&a)  7 using namespace std;  8 #define N 61  9 char dp[N][N][N][100],a[100]; 10 void init() 11 { 12     strcpy(dp[0][0][0],"1\0"); 13     strcpy(dp[1][1][0],"1\0"); 14     strcpy(dp[1][0][1],"0\0"); 15     strcpy(dp[1][0][0],"1\0"); 16 } 17  18 void add(char *p) 19 { 20     int x,l,i,jin=0; 21     l=strlen(a); 22     int now=0; 23     for(i=0;p[i]!='\0';i++) 24     //从加数开始一位一位访问 25     { 26         if(i>=l) 27             x=p[i]-'0'+jin;//i超过了a的长度 28         else 29             x=p[i]-'0'+a[i]-'0'+jin; 30         if(x>9) 31         { 32             jin=x/10; 33             x%=10; 34         } 35         else 36             jin=0; 37         a[now++]=x+'0'; 38     } 39     while(jin) 40     { 41         if(l<=now) 42         { 43             a[now++]=(jin%10)+'0'; 44             jin/=10; 45         } 46         else 47         { 48             x=a[now]-'0'; 49             x+=jin; 50             if(x>10) 51             { 52                 jin=x/10; 53                 x%=10; 54             } 55             else 56                 jin/=10; 57             a[now++]=x+'0'; 58         } 59     } 60     if(now>l) 61         a[now]='\0'; 62 } 63  64 void put(int x) 65 { 66     int l=strlen(dp[x][x][x]); 67     for(int i=l-1;i>=0;i--) 68         cout<
           
            j&&j>=k) 88 add(dp[i-1][j][k]); 89 if(j>k) 90 add(dp[i][j-1][k]); 91 if(k>0) 92 add(dp[i][j][k-1]); 93 strcpy(dp[i][j][k],a); 94 } 95 } 96 } 97 while(~scanf("%d",&n)) 98 { 99 put(n);100 }101 return 0;102 }