nyoj_758_分苹果

分苹果

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描述: 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

（注意：假如有3个盘子7个苹果，5，1，1和1，5，1 是同一种分法。）

输入

t，表示测试组数（t<=10）然后t行，每行包含两个数M,N.(1<=M,N<=10)

输出

输出不同的分法

样例输入

1
7 3

样例输出

上传者

TC_常红立

方法一：母函数

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

方法二：递归----类似整数划分

 1 #include <stdio.h>
 2 int f(int m,int n)
 3 {
 4     if(m==1||n==1||m==0)
 5     return 1;
 6     if(m<n)
 7     return f(m,m);
 8     return f(m,n-1)+f(m-n,n);
 9 }
10 int main()
11 {
12     int T;
13     scanf("%d",&T);
14     while(T--)
15     {
16         int m,n;
17         scanf("%d%d",&m,&n);
18         printf("%d
",f(m,n));
19     }
20     return 0;
21 } 
22 //AC