放苹果

题意

把 $m$ 个同样的苹果放在 $n$ 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法。 $5,1,1$ 和 $1,1,5$ 是同一种分法。

以样例 $m=7,n=3$ 为例，不同的分法如下表所示：

盘子1	盘子2	盘子3
0	0	7
0	1	6
0	2	5
0	3	4
1	1	5
1	2	4
1	3	3
2	2	3

表格的每一行是 3 个盘子分别放的苹果数，且行内从左到右不下降。不同的分法只看“每盘几个”的集合、不看排列，因此共 8 行，正是样例输出 8。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 15:26
 * update_at: 2026-07-31 15:27
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举所有可能。
// 每一层为第 depth 个盘子选择一个苹果数（0..m），
// 到叶子节点统一检查：总数等于 m，且序列不下降，这样每个分法只被数一次。
#include <bits/stdc++.h>
using namespace std;

int m, n;
int choose[15]; // choose[i] 记录第 i 个盘子选了几个苹果
int ans;        // 当前一组数据的答案

void dfs(int depth) {
    if (depth == n + 1) {
        // 完整选择序列已生成，在叶子统一检查合法性。
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += choose[i];
        }
        if (sum != m) {
            return;
        }

        // 同一组分法只保留“不下降序列”这一种写法，避免重复计数。
        for (int i = 2; i <= n; i++) {
            if (choose[i] < choose[i - 1]) {
                return;
            }
        }
        ans++;
        return;
    }

    // 第 depth 个盘子可以选择 0..m 个苹果。
    for (int i = 0; i <= m; i++) {
        choose[depth] = i;
        dfs(depth + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        cin >> m >> n;
        ans = 0;
        dfs(1);
        cout << ans << endl;
    }
    return 0;
}

这个暴力把问题看成一串选择序列：第 i 个盘子选择放几个苹果（ $0..m$ ）。递归先生成完整的 choose[1..n]，到叶子再统一检查“总数等于 $m$ ”和“序列不下降”两个条件。其中“序列不下降”是去重的关键：同一个分法只保留排序后那一种写法。这种写法枚举了全部 $(m+1)^n$ 种分配， $m=n=10$ 时不可行，但能清楚看出枚举对象。

优化思路是把“先生成、后检查”改成“边生成、边约束”：

第 $i$ 个盘子至少放 $a_{i-1}$ 个苹果，保证序列不下降，从而消除重复；
第 $i$ 个盘子至多放剩余苹果数，保证总和不超过 $m$ ；
最后一个盘子不再枚举，直接把剩余苹果全部给它。

这样每个合法分法恰好被枚举一次，计数总和就是答案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 15:26
 * update_at: 2026-07-31 15:27
 */
// P2386 放苹果：DFS 枚举不下降序列，统计不同分法。
#include <bits/stdc++.h>
using namespace std;

int m, n;    // m 个苹果，n 个盘子
int ans;     // 当前一组数据的答案
int a[15];   // a[i] 记录第 i 个盘子放的苹果数，保证 a[1] <= a[2] <= ... <= a[n]

// 当前在填第 depth 个盘子，还剩 apple 个苹果没放。
// 为了保证序列不下降，第 depth 个盘子至少要放 a[depth-1] 个。
void dfs(int depth, int apple) {
    if (depth == n) {
        // 最后一个盘子吃掉所有剩下的苹果；
        // 只要它不比前一个盘子少，就得到一个合法的分法。
        if (apple >= a[depth - 1]) {
            ans++;
        }
        return;
    }

    // 枚举第 depth 个盘子放 i 个苹果：
    // i 既要不小于前一个盘子，又不超过剩余苹果数。
    for (int i = a[depth - 1]; i <= apple; i++) {
        a[depth] = i;
        dfs(depth + 1, apple - i);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        cin >> m >> n;
        ans = 0;
        dfs(1, m);
        cout << ans << endl;
    }
    return 0;
}

复杂度

朴素枚举为 $O((m+1)^n)$ ，不可行。最终 DFS 访问的节点数是 $m$ 分成不超过 $n$ 个不下降部分的实际状态数，在 $m,n \leqslant 10$ 时极小，瞬间完成。

空间复杂度 $O(n)$ ，只用全局数组 a[15]。

总结

这道题的核心观察是：盘子和苹果都“同样”，分法与顺序无关，因此每个分法恰好对应一个不下降序列。DFS 用下界剪枝消除重复、用上界剪枝避免超总数，是整数划分计数的入门题。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6
7m 个同样的苹果 + n 个同样的盘子
`- 关键观察：分法顺序无关，每个分法唯一对应一个“不下降序列”
   `- DFS 从第 1 个盘子开始逐盘填数
      |- 每盘至少放前一盘那么多（不下降）
      |- 每盘不超过剩余苹果数
      `- 最后一个盘子吃掉全部剩余苹果，满足不下降就计数
         `- 计数总和 = 不同分法数

先看“不下降序列”这个关键观察，它把重复计数问题变成了唯一表示问题。再顺着 DFS 的三个约束，理解它为什么只枚举出所有合法分法而不会重复。最终计数自然就是答案，这也是样例输出 8 的来源。

目录

题意

思路

代码

复杂度

总结

图示解析