pku acm 1664 分苹果－－仿整数划分

放苹果

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 6538		Accepted: 4084

Description
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

Output
对输入的每组数据M和N，用一行输出相应的K。

Sample Input

1
7 3

Sample Output

8

/*

道行不够，看到这题时想到了王晓东的整数划分，但是构造递归式时依旧猛出错。。。最后还是看discuss里面first的递归式，感觉真是相当精妙。。放在这里慢慢品味。。
f(m, n) = f(m-n, n) + f(m, n-1)

f(m, n): 把m个苹果放到n个盘子中的方法数
f(m, n-1): 把m个苹果放到n-1个盘子中的方法数(其中至少有一个空盘子)
f(m-n, n): 把m个苹果放到n个盘子中,而且每个盘子中都有苹果(先拿n个出来,等m-n个放好了,然后每个盘子放一个)
*/

//源码，只是没想到用递归也是0MS，想来是数据规模小的缘故。
#include
using namespace std;
int f(int m,int n);
int main()
{
 int t,m,n,an;
 cin>>t;
 while(t--)
 {
  cin>>m>>n;
  an=f(m,n);
  cout< }
 return 0;
}
int f(int m,int n)
{
 if(m==0||m==1) return 1;
 if(n==0||n==1) return 1;
 if(m else return f(m-n,n)+f(m,n-1);
}