根据盘子的数量来画出解答树的层次。得到解的结构。明白解答树后就可以想到用dfs了。
#include<cstdio> using namespace std; int n,m,cnt; int s[3] = {0,0,0}; int main() { void dfs(int x,int y); int k; scanf("%d",&k); while(k--) { cnt = 0; scanf("%d %d",&n,&m); dfs(1,0); printf("%d\n",cnt); } return 0; } void dfs(int x,int y) // x表示用了几个盘子,y表示剩余的苹果数 { if(x == m) { if(n-y >= s[x-1]) { s[x] = n-y; cnt = cnt+1; for(int i = 0 ; i < 3 ; i++) { printf("%d",s[i]); } putchar(10); } return; } for(int i = 0 ; i < n ; i++) { if(i>=s[x-1]) { y = y + i; s[x] = i; x = x+1; dfs(x,y); y = y - i; //回溯返回操作。 x = x - 1; } } }