[NOIP 2012 普及组] 摆花

题意

有 n 种花，每种花最多可以摆 a_i 盆。

现在要在门口摆出一排共 m 盆花，并且：

同一种花必须摆在一起
不同种花按编号从小到大依次摆放

问一共有多少种不同的摆花方案。

这张表把题意翻成了计数背包模型：

原题对象	背包含义
一种花	一个有数量上限的物品
摆 `k` 盆这种花	选择 `k` 次
总盆数 `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
50
51#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000007;

int n, m;
vector<int> a;
vector<int> choose_flower; // choose_flower[i] 表示第 i 种花取多少盆
int answer = 0;

int calc_total() {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += choose_flower[i];
    }
    return total;
}

// dfs_choose 只负责枚举每种花取多少盆，最后统一检查总数。
void dfs_choose(int dep) {
    if (dep == n) {
        if (calc_total() == m) {
            answer++;
            if (answer >= MOD) answer -= MOD;
        }
        return;
    }

    // 第 dep 种花可以取 0..a[dep] 盆。
    for (int cnt = 0; cnt <= a[dep]; cnt++) {
        choose_flower[dep] = cnt;
        dfs_choose(dep + 1);
    }
}

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

    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    choose_flower.assign(n, 0);
    dfs_choose(0);
    cout << answer << '\n';

    return 0;
}

brute.cpp 把每种花取多少盆看成一层选择：choose_flower[i] 表示第 i 种花取几盆。递归先生成完整计数序列，叶子节点再检查是否正好摆出 m 盆。

这个做法正确，但复杂度很高，只适合小数据验证。

关键观察是：

每种花有数量上限，所以不是无限背包。
我们统计的是方案数，不是最大值。
多重背包可以用“前缀和优化”把转移从 $O(a_i)$ 降到 $O(1)$ 。

于是设：

dp[j] 表示处理到当前花种后，摆出 j 盆的方案数

对于第 i 种花，最多放 a_i 盆时：

cur[j] = prev[j] + prev[j-1] + ... + prev[j-a_i]

这正好可以用滑动窗口 / 前缀和来维护。

DP 公式

设 $prev_j$ 表示处理完前 $i-1$ 种花后摆出 $j$ 盆的方案数， $cur_j$ 表示处理完第 $i$ 种花后的方案数。若第 $i$ 种花最多摆 $a_i$ 盆，则：

cur_j=\sum_{x=0}^{\min(a_i,j)} prev_{j-x}

用前缀和可以把它写成：

cur_j=prefix_j-prefix_{j-a_i-1}

最终答案为：

dp_m

公式解释：处理第 i 种花时，如果最终总数是 j，这种花可以贡献 0..a_i 盆。直接求和会多一层枚举，用前缀和把这段连续的旧状态一次算出来。

样例 DP 表格

以样例为例： $n = 2, m = 4$ ，两种花最多分别摆 $3, 2$ 盆。

处理花种	上限 $a_i$	$dp_0$	$dp_1$	$dp_2$	$dp_3$	$dp_4$
初始	—	1	0	0	0	0
花种 1	3	1	1	1	1	0
花种 2	2	1	2	3	3	2

花种 2 的转移细节： $cur_4 = dp_4 + dp_3 + dp_2 = 0 + 1 + 1 = 2$ （花种 2 摆 0、1、2 盆时，花种 1 分别摆 4、3、2 盆，但花种 1 最多 3 盆，所以 $dp_4 = 0$ 不贡献）。

答案 $dp_4 = 2$ ，对应两种方案：花种 1 摆 2 盆 + 花种 2 摆 2 盆，或花种 1 摆 3 盆 + 花种 2 摆 1 盆。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000007;

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

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // prev[j]：已经处理完前 i-1 种花后，摆出 j 盆花的方案数
    vector<int> prev(m + 1, 0), cur(m + 1, 0);
    prev[0] = 1;

    for (int i = 1; i <= n; i++) {
        cur[0] = 1;
        for (int j = 1; j <= m; j++) {
            long long val = cur[j - 1] + prev[j];
            if (j - a[i] - 1 >= 0) {
                val -= prev[j - a[i] - 1];
            }
            val %= MOD;
            if (val < 0) val += MOD;
            cur[j] = static_cast<int>(val);
        }
        swap(prev, cur);
    }

    cout << prev[m] << '\n';

    return 0;
}

复杂度

时间复杂度： $O(nm)$
空间复杂度： $O(m)$

总结

这题本质上是“有限数量的计数背包”。

如果直接枚举每种花用了多少盆，复杂度会偏高；用前缀和把一段连续转移一次算完，就能把多重背包优化到线性级别。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。