POJ 1664 放蘋果

想法：

　　因為盤子皆一樣，例如(1,1,3)和(1,3,1)是同樣的，所以排的時候以遞增的方式排，只保留(1,1,3)這組，故左邊的數字不大於右邊的數字。在一開始(0,0,0)時，若最左邊的盤子要+1，則右邊兩個也要跟著+1才能使上面的條件成立，照此規則，當某個盤子要+1時，其右邊的盤子也要跟著+1，所以要注意此動作是否會造成蘋果不夠(if(m-i>=0))，而當蘋果剛好分完(m=0)或是只剩最右邊的盤子(n=1)時，遞迴結束。

	#include<cstdio>
	using namespace std;
	long long int sum=0;
	void func(int m,int n);
	int main()
	{
	int t,m,n,i,j;
	scanf("%d",&t);
	while(t--){
	sum=0;
	scanf("%d %d",&m,&n);
	func(m,n);
	printf("%lld\n",sum);
	}
	return 0;
	}
	void func(int m,int n) //m顆蘋果分n堆
	{
	if(m==0 || n==1) {
	sum++;
	return ;
	}
	int i,j;
	for(i=n;i>=1;i++){ //n堆~1堆
	if(m-i>=0)
	func(m-i,i);
	}
	}

view raw [POJ] 1664 放蘋果.cpp hosted with ❤ by GitHub