首页 > 代码库 > HDU 2069二维母函数

HDU 2069二维母函数

显然母函数,有一个地方需要注意。当输入0时,只有一种方法,所以输出1。

代码:

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <iostream>
 5 using namespace std;
 6 int c1[255][111], c2[255][111];
 7 main()
 8 {
 9     
10     int n, i, j, k, l;
11     int a[]={0,1,5,10,25,50};
12     while(scanf("%d",&n)!=EOF)
13     {
14         if(n==0){                          //n==0
15             cout<<1<<endl;
16             continue;
17         }
18         memset(c1,0,sizeof(c1));
19         memset(c2,0,sizeof(c2));
20         for(i=0;i<=n&&i<=100;i++)       //初始边界 
21         c1[i][i]=1;
22         for(i=2;i<=5;i++)
23         {
24             for(j=0;j<=n;j++)
25             {
26                 for(k=0;k*a[i]+j<=n;k++)
27                 for(l=0;l+k<=100;l++)
28                 c2[k*a[i]+j][l+k]+=c1[j][l];
29             }
30             for(k=0;k<=n;k++)
31             {
32                 for(l=0;l<=100;l++)
33                 {
34                     c1[k][l]=c2[k][l];
35                     c2[k][l]=0;
36                 }
37             }
38         }
39         int sum=0;
40         for(l=0;l<=100;l++)
41         sum+=c1[n][l];
42         printf("%d\n",sum);
43     }
44 }