摘要
Title: 3428. 放苹果
Tag: 整数划分
Memory Limit: 64 MB
Time Limit: 1000 ms

3428. 放苹果

题意

把 M 个同样的苹果放在 N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
盘子相对顺序不同，例如 5，1，1 和 1，5，1 算作同一种分法。
思路

整数划分板子题

做这题之前可以回顾一下计数类 DP 中的整数划分问题，二者存在一定的相似性。

状态表示：dp[i][j]

集合：所有总和是 i，且恰好放在 j 个盘子的方案。

属性：分法数量。

状态计算：

方案中最小值是1：去掉一个1，即f[i-1, j-1]

方案中最小值大于1：每个数都减去1，即f[i-j, j]

通过上述两种情况，可得状态转移方程：f[i, j] = f[i-1, j-1] + f[i-j, j]

通过该方式进行状态计算，可以确保 n 个盘子中的苹果数满足 $n1≥n2≥…≥nkn1≥n2≥…≥nk$ 。由于该特性，可以确保不重不漏。

边界条件：dp[0][0] = 1，即 0 个苹果放 0 个盘子中的方案数为1。

因为允许有些盘子空着不放，所以最终的答案即为：f[m][1]+f[m][2]+...+f[m][n]

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-08-04 17:01:35
* @FilePath: \Acwing\3428\3428.cpp
* @LastEditTime: 2022-08-06 01:53:03
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int INF = INT_MAX;
const int N = 1e6 + 10;

signed main()
{
    IOS;
    int m, n;
    while (cin >> m >> n)
    {
        vector<vector<int>> dp(11, vector<int>(11, 0));
        // m个放进n个盘子
        dp[0][0] = 1;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= i; ++j)
            {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
            }
        }
        int res = 0;
        for (int j = 1; j <= n; j++)
        {
            res += dp[m][j];
        }
        cout << res << '\n';
    }
    return 0;
}

3428. 放苹果

题意

思路

代码