A21140.放苹果 详细题解

这道题我分了三个情况来讨论：

情况1.当苹果没了：
那么也只有一种分法（因为题目允许空盘）

情况2.当盘子或苹果的数量都是1时：
那么分法只有一种（这个很容易理解）

情况3.当盘子比苹果多时;
那最少也有pan - guo个空盘，（也就是1个苹果1个盘，保证空盘最少的最优解）
那这pan - guo个空盘被撤走了之后并不影响最后的结果，所以这个问题可以转化乘盘子等于苹果的情况（情况4）

情况4.当盘子的数量 等于 或 大于 苹果的数量时：
为什么等于和大于这两种情况能够放在一起？

因为这两种情况的思路其实是一样的，分 两块 来看：

（1）：至少有一个盘子是空的：
既然允许空盘，我们可以假设第 pan 个盘子是空的，
那么问题就转化为：将guo个苹果放入剩下的 pan−1 个盘子中
即f(guo,pan - 1);
（pan - 1 可以理解为减少一个可用盘子）

（2）：每个盘子至少有1个苹果：
既然每个盘子至少有1个苹果，那就还有guo - pan个苹果没有放
那么问题就转化为：将剩下的guo - pan个苹果放进pan个盘子里
即f（guo - pan，pan）；

#include <bits/stdc++.h>
using namespace std;
int m,n;
int f(int guo,int pan)
{
//情况1
	if(guo == 0)
	{
		return 1;
	}
//情况2
    else if(pan == 1 || guo == 1)
    {
        return 1;
    }
//情况3
    else if(pan > guo)
	{
		return f(guo,guo);
	}
//情况4
    else
    {
        return f(guo,pan - 1) + f(guo - pan,pan);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i = 0;i < t;i++)
    {
        scanf("%d%d",&m,&n);
        printf("%d\n",f(m,n));
    }
    return 0;
}

提醒：不要复制代码！！！