题解 | #放苹果#

来一个和大佬们思路不太一样的解法，希望能起到启发思路的作用。也欢迎各路朋友讨论和指正

题目中规定'1 5 1' 和'5 1 1'是同样的组合，那么对于m个苹果和n个盘子，记$x_{i}x\_i$是第$ii$个盘子中的苹果数,可以认为满足非升序（或非降序）排列

我们将问题理解成（m）个苹果、（n）个盘子和最大数值为（$x_0=mx\_0=m$）的一个问题，记为$f(x_0,m,n)f(x\_0,m,n)$

那么此时往第一个盘子中摆放苹果的个数为$kk$个

则约束表达式变为

问题就变成了（$m-x_{1}m-x\_1$）个苹果、（n-1）个盘子和上一个盘子内的苹果数为（$x_{1}x\_1$）的问题，记为 $f(x_1,m-x_1,n-1)f(x\_1,m-x\_1,n-1)$

更为一般性，我们记上一个盘子苹果数为$x_{last}x\_\{last\}$, 当前剩余苹果数为$m_{left}m\_\{left\}$，当前盘子数为$n_{left}n\_\{left\}$. 此时问题记为$f(x_{last},m_{left},n_{left})f(x\_\{last\},m\_\{left\},n\_\{left\})$

只要不是只剩下一个盘子，当前问题的第一个盘子里，尝试放置从$\min (x_{last},m_{left})\backslash min(x\_\{last\},m\_\{left\})$~~0个苹果，将其结果归结为子问题的求和

经过不断的嵌套之后，问题总归会来到最后一个盘子n = 1的情形，此时剩下的苹果全部放入最后的盘子，只需要满足降序排列条件即可视为存在该排列，不满足降序要求则认为是重复排列。 约束问题变为

递归的程序设计如下所示，调用过程需注意初始化为$f(m,m,n)f(m,m,n)$

#include<stdio.h>

int Partition(int xlast,int mleft,int nleft)
{
    int x_now;
    int cnt = 0;
    int tmp;
    if(nleft == 1)
    {
        if(mleft > xlast) // 不满足降序
            return 0;
        else 
            return 1;
    }        
    for(x_now = (mleft>xlast?xlast:mleft); x_now >= 0; x_now--) // min(mleft, xlast)
    										// (mleft>xlast?xlast:mleft)
    {
        tmp = Partition(x_now, mleft - x_now, nleft - 1);
        if(tmp)
            cnt+=tmp;
        else // 减少部分不必要的计算
            break;
    }    
    return cnt;
}

int main()
{
    int m,n ;
    int cnt = 0;
    while(scanf("%d %d",&m,&n)!=EOF)
    {
        cnt = Partition(m,m,n);
    }
    printf("%d",cnt);
    return 0;
}