随笔-65  评论-6  文章-0  trackbacks-0
 1 //dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1];
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 #define MaxSize 100
 6 char num[62][MaxSize],dp[62][62][62][MaxSize];
 7 inline int max(int a,int b){
 8     return a>b?a:b;
 9 }
10 void sum(char *a,char *b){
11     int i,k,m=a[0],n=b[0];
12     a[0]=k=max(m,n);
13     for(i=1;i<=k;i++){
14         a[i]+=b[i];
15         if(a[i]>9){
16             a[i+1]++;
17             a[i]%=10;
18             if(i+1>k){
19                 k++;
20                 a[0]++;
21             }
22         }
23     }
24 }
25 void cpy(char *a,char *b){
26     int i;
27     for(i=0;i<=b[0];i++)
28         a[i]=b[i];
29 }
30 void add(int x,int y,int z){
31     if(x-1>=0&&x-1>=y&&y>=z)
32         sum(dp[x][y][z],dp[x-1][y][z]);
33     if(y-1>=0&&x>=y-1&&y-1>=z)
34         sum(dp[x][y][z],dp[x][y-1][z]);
35     if(z-1>=0&&x>=y&&y>=z-1)
36         sum(dp[x][y][z],dp[x][y][z-1]);
37 }
38 void solve(){
39     int i,j,k;
40     memset(dp,0,sizeof(dp));
41     dp[0][0][0][0]=dp[0][0][0][1]=1;
42     for(i=1;i<=60;i++)
43         for(j=0;j<=i;j++)
44             for(k=0;k<=j;k++){
45                 add(i,j,k);
46                 if(i==j&&j==k)
47                     cpy(num[i],dp[i][j][k]);
48             }
49 
50 }
51 int main(){
52     //freopen("in.txt","r",stdin);
53     solve();
54     int i,n;
55     while (~scanf("%d",&n)){
56         for(i=num[n][0];i>0;i--)
57             printf("%d",num[n][i]);
58         printf("\n\n");
59     }
60     return 0;
61 }
posted on 2012-07-11 16:09 Leo.W 阅读(174) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理