[NOIP2012-普及] 摆花

题目描述

有 $n$ 种花，第 $i$ 种最多摆 $a_i$ 盆。要把 $m$ 盆花摆成一排，要求同种花连续、不同种类按编号从小到大依次出现。求合法摆法总数，答案对 $1000007$ 取模。

输入格式：第一行 $n, m$ ；第二行 $n$ 个整数 $a_1 \dots a_n$ 。
输出格式：一个整数，表示方案数对 $1000007$ 取模的结果。
样例输入：2 4 / 3 2　样例输出：2

数据范围： $0 < n \leqslant 100,\ 0 < m \leqslant 100$ 。

思路

设 $f[j]$ 为前若干种花恰好摆 $j$ 盆的方案数。加入第 $i$ 种花时， $f[j]$ 等于上一阶段 $dp[j-a_i..j]$ 的滑动窗口和。用前缀和把单格求和压到 $O(1)$ ，一维滚动数组即可，总复杂度 $O(n \cdot m)$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-10-02 09:40
# update_at: 2026-10-02 09:40

import sys
from itertools import accumulate

MOD = 1000007  # 题面指定的模数（不是常见的 10^9+7）


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    caps: list[int] = [min(next(data), m) for _ in range(n)]  # 超过 m 的上限永远用不到

    # dp[x] = 摆 x 盆花的方案数；逐种花做「长度 cap+1 的滑动窗口和」
    dp = [0] * (m + 1)
    dp[0] = 1  # 一种花都不摆
    for cap in caps:
        pre = list(accumulate(dp, initial=0))  # pre[x] = 摆前若干盆的方案数前缀和
        # 新方案数 = 窗口 dp[x-cap..x] 的和 = pre[x+1] - pre[x-cap]（下标截到 0）
        dp = [(pre[x + 1] - pre[max(x - cap, 0)]) % MOD for x in range(m + 1)]

    print(dp[m])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-06 14:55
 * update_at: 2026-10-06 14:55
 */

#include <cstdio>
using namespace std;

typedef long long ll;

const int MOD = 1000007; // 题面指定的模数

int n, m;
int a[105];       // 每种花最多摆的盆数
int dp[105];      // dp[j] = 当前阶段恰好摆 j 盆的方案数
int pre[105];     // pre[j] = dp[0..j] 的前缀和

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (a[i] > m) a[i] = m; // 超过 m 的上限永远用不到
    }

    dp[0] = 1; // 一种花都不摆，只有摆 0 盆一种方案

    for (int i = 1; i <= n; i++) {
        int cap = a[i];
        // 先对旧 dp 做前缀和
        pre[0] = dp[0];
        for (int j = 1; j <= m; j++) {
            pre[j] = pre[j - 1] + dp[j];
            if (pre[j] >= MOD) pre[j] -= MOD;
        }
        // 用前缀和差分求滑动窗口和，得到新 dp
        for (int j = 0; j <= m; j++) {
            int left = j - cap - 1;
            int val = pre[j];
            if (left >= 0) {
                val -= pre[left];
                if (val < 0) val += MOD;
            }
            dp[j] = val;
        }
    }

    printf("%d\n", dp[m]);
    return 0;
}

[NOIP2012-普及] 摆花

目录

题目描述

思路

参考代码