Input 第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。 Output 对输入的每组数据M和N，用一行输出相应的K。 Sample Input
1 7 3Sample Output
8 这是一道递推题，但也可用dfs来搜索； #include <stdio.h> int fun(int m,int n)//n为盘子数，m为苹果数 { if(m==0||n==1) return 1; if(n>m) return fun(m,m);//如果苹果数比盘子少，则n-m个盘子是空的，所以相当于在m个盘子里放苹果，即f（m，n）=f（m，//m） else return fun(m,n-1)+fun(m-n,n);//如果苹果比盘子多，则有两种情况，一种是有盘子没苹果，则放下一个盘子，则f（//m,n-1）.另一种是每个盘子都有苹果，每个盘子取走一个苹果不影响排放结果，即f（m-n,n）;两者相加即可 } int main() { int T,m,n; scanf("%d",&T); while(T--) { scanf("%d %d",&m,&n); printf("%d\n",fun(m,n)); } return 0; } 另一种做法就是用DFS搜索 由题可知，每个盘子都一样，可以任意放，要不能重复种数，那么可以这样假设：设1到n个盘子放平果的数量为a1,a2,a3,......,an.并且a1+a2+a3+.....+an=sum(平果总数)。如果a1<=a2<=a3<=.....<=an,即a(n-1)<=an.这样就不会重复。现在关建在于第i个盘最多放多少个平果。设第i个盘最多放maxi个平果，那么maxi=sum/(n-i);这样都搞定之后，用dfs确定每个盘放平果的数量，当都满足a(n-1)<=an时，就算是一种。把满足条件的种数加起来就是n个盘放sum个平果的种数。 #include<stdio.h> int max[15],n,m;//n盘子数，m为平果数 void setmax()//计算每个盘最多放多少个 { for(int i=0; i<n; i++) max[i+1]=m/(n-i); } int dfs(int sum,int p,int v)//sum为放好的平果数，p是第v-1个盘放的平果数 { int ans=0; if(v==n&&m-sum>=p)//m-sum是用在第n个盘放的平果 return 1; if(v==n) return 0; for(int s=p; s<=max[v]; s++) //从p开始，满足a(v-1)<=a(v). ans+=dfs(sum+s,s,v+1); return ans; } int main() { int t,ans[15][15]= {0}; scanf("%d",&t); while(t--) { scanf("%d%d",&m,&n); setmax(); if(ans[n][m]==0) ans[n][m]=dfs(0,0,1); printf("%d\n",ans[n][m]); } }