HDU 1028 Ignatius and the Princess III

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

思路整数的划分问题和分苹果问题应该差不多。

套用组合数学母函数模板

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 int main()
 4 {
 5     int num1[200];
 6     int num2[200];
 7     int n,i,j,k;
 8     while(~scanf("%d",&n))
 9     {
10         for(i=0;i<=n;i++)
11         {
12             num2[i]=0;
13             num1[i]=0;
14         }
15   for(i=0;i<=n;i++)
16   {
17    num1[i]=1;
18   }
19         for(i=2;i<=n;i++)
20         {
21                 for(j=0;j<=n;j++)
22                  {
23                     for(k=0;k+j<=n;k+=i)
24                     {
25                         num2[k+j]+=num1[j];
26                     }
27             }
28             for(j=0;j<=n;j++)
29             {
30                 num1[j]=num2[j];
31                 num2[j]=0;
32             }
33         }
34         printf("%d\n",num1[n]);
35     }
36     return 0;
37 }