随笔 - 32  文章 - 2  trackbacks - 0
<2008年6月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8782
  • 排名 - 1247

最新评论

阅读排行榜

评论排行榜

http://acm.timus.ru/problem.aspx?space=1&num=1036
简单的DP,要注意细节的处理,s为奇数,s最大值为1000(n=50 s=1000,answer=0)
 1 #include <iostream>
 2 using namespace std;
 3 int n,s;
 4 int f[600][51];
 5 
 6 void jia(int a[51],int b[51]){
 7     for (int i=1;i<=50;++i) a[i]+=b[i];
 8     for (int i=1;i<50;++i){
 9         a[i+1]+=a[i]/10000;
10         a[i]%=10000;
11         }
12     }
13     
14 void cheng(int a[51],int b[51]){
15     int c[111];
16     for (int i=1;i<=110;++i) c[i]=0;
17     for (int i=1;i<=50;++i)
18         for (int j=1;j<=50;++j) c[i+j-1]+=a[i]*b[j];
19     for (int i=1;i<=50;++i){
20         c[i+1]+=c[i]/10000;
21         c[i]%=10000;
22         }
23     for (int i=1;i<=50;++i) a[i]=c[i];
24     }
25 
26 int main(){
27     scanf("%d %d",&n,&s);
28     if (s%2==1) cout<<0;
29     else{
30         s/=2;
31         for (int i=0;i<10;++i) f[i][1]=1;
32         for (int i=1;i<n;++i)
33             for (int j=450;j>0;--j)
34                 for (int k=1;k<=9&&j>=k;++k) jia(f[j],f[j-k]);
35         cheng(f[s],f[s]);
36         int p=50;
37         while (f[s][p]==0&&p>0--p;
38         if (p==0) cout<<0;
39         else{
40             printf("%d",f[s][p]);
41             for (int i=p-1;i>0;--i) printf("%04d",f[s][i]);
42             }
43         }
44     }
45     
46 


posted on 2008-11-04 17:52 Joseph 阅读(425) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理