形式化题目

给定 $n$ 种面值 $b_1 < b_2 < \cdots < b_n$，第 $i$ 种硬币最多可用 $c_i$ 枚。 求非负整数 $t_1, \dots, t_n$ 满足

使得硬币总数 $\sum_{i=1}^{n} t_i$ 最小，输出这个最小值。

样例：$n=3$，面值 $(2,3,5)$，数量 $(2,2,1)$，目标 $k=10$。

1
2
3
43
2 3 5
2 2 1
10

最优付法是 $5 + 3 + 2 = 10$ 共 3 枚（两枚 5 不行，5 只有 1 枚； $2+2+3+3$ 要 4 枚），输出 3。

正解

思路

建模。 设 dp[v] = $ 恰好凑出面值 $v 所需的最少硬币数（不可达记为 $\infty$）， $dp[0] = 0$。对每种面值 $(w, c)$ 做一次松弛：

处理完全部 $n$ 种面值后 $dp[k]$ 即答案。

先排除两个直觉做法。 贪心"面值从大到小取"是错的：面值 $1,3,4$、$k=6$ 时 贪心取 $4+1+1=3$ 枚，而 $3+3$ 只要 2 枚——非规范币制下最优解不具贪心子结构。 逐枚处理硬币（每枚扫一遍 $0 \sim k$）虽然正确，复杂度 $O(k \sum c_i)$， 按数据量最坏 $2\times10^4 \times (200 \times 2\times10^4) = 8\times10^{10}$，完全不可行。

瓶颈与中间站。 瓶颈在"一种面值用 $t$ 枚"被拆成 $t$ 次独立松弛，同一子问题反复重算。 经典救法是二进制拆分：把 $c$ 枚打包成 $O(\log c)$ 个 0-1 物品，降到 $O(k \sum \log c_i) \approx 6\times10^7$——C++ 能过，Python 偏慢。 而数据规模 $n \leqslant 200$、$k \leqslant 2\times10^4$ 提示存在 $O(nk) = 4\times10^6$ 这一档的做法，即同余类 + 单调队列。

观察一：转移按同余类封闭。 转移 $v \leftarrow v - tw$ 中 $v$ 与 $v-tw$ 模 $w$ 同余， 所以 $dp'[v]$ 只依赖 $dp$ 在同余类 $r = v \bmod w$ 中的值。把 $0 \sim k$ 按模 $w$ 分成 $w$ 条互不干扰的线，类内第 $m$ 个位置记作 $v = r + mw$：

观察二：换元后是滑动窗口。 令 $u = m - t$（从 $v$ 往回退 $u$ 个位置），$t = m - u$：

每个 $m$ 只看固定长度的窗口 $[m-c, m]$，窗口每步右移一格、只进一出一—— 标准滑动窗口最小值。用单调队列按下标递增、键 $old[r+uw]-u$ 递增维护： 入队前弹出队尾所有键 $\geqslant$ 自己的下标（它们以后永远轮不到当最小值）， 队首滑出窗口就出队，队首即窗口最小值。每个位置入队、出队各一次，摊还 $O(1)$。

用样例走一遍，$dp[v]$ 按面值分阶段推进（$\infty$ 表示当前不可达）：

注意 $dp[9]=\infty$ 这一格：$t=0,1,2$（$t=3$ 超过 $c_3=2$ 的限制）对应的候选 $old[9]$、$old[6]$、$old[3]$ 全部不可达——数量上限正是通过窗口长度 $c$ 生效的。最后一行 $dp[10] = old[5] + 1 = 3$，即样例输出。

再单独看同余类 $r=1$ 在面值 $w=3$、数量 $c=2$ 这一阶段的滑窗过程 （old 取上表"加入 $(2,2)$"行）：

队列里只有 $u=1$（键 1）是有效最小值：不可达位置的键是 $\infty$，要么入队前被淘汰、 要么排在有效键后面。窗口每移一格直接读队首，绝不重新扫窗口。

正确性靠归纳：old 是"只用前 $i-1$ 种面值"的最优表，枚举第 $i$ 种用 $t$ 枚的 所有合法取值即得"用前 $i$ 种"的最优表；单调队列只是把窗口 $\min$ 换成摊还 $O(1)$ 的 等值计算——队列内下标递增、键递增，队首恒为窗口内最小键，两个不变量由 "队尾淘汰"与"队首过期弹出"两条规则维持。

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#!/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-09-30 21:17
# update_at: 2026-09-30 21:26

import sys
from collections import deque

INF = 10**9  # 不可达哨兵（真实答案至多 k，远小于它）


def relax(old: list[int], dp: list[int], w: int, c: int, k: int) -> None:
    """加入面值 w、数量不超过 c 的硬币：对每个同余类做单调队列优化的有界松弛。"""
    if w > k:  # 面值超过目标的硬币一枚也用不上
        return
    # 位置 r+m*w 上（m 表示"该类里第几个位置"）：
    # dp[r+m*w] = min_{t<=c} old[r+(m-t)*w] + t = m + min_{u in [m-c, m]} (old[r+u*w] - u)
    # 窗口 [m-c, m] 只向右滑动，用单调队列维护键 old[r+u*w] - u 的最小值。
    for r in range(w):  # 同余类内部位置等距 w，类间互不干扰
        dq: deque[int] = deque()
        m = 0
        while (pos := r + m * w) <= k:
            key = old[pos] - m  # 候选下标 u=m 的键
            while dq and old[r + dq[-1] * w] - dq[-1] >= key:
                dq.pop()  # 队尾更差的下标不可能再成为最小值
            dq.append(m)
            while m - dq[0] > c:  # 队首滑出窗口 [m-c, m]
                dq.popleft()
            dp[pos] = m + old[r + dq[0] * w] - dq[0]
            m += 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    values = [next(data) for _ in range(n)]  # 面值 b_i（严格递增）
    counts = [next(data) for _ in range(n)]  # 各面值数量 c_i
    k = next(data)  # 要凑的目标面值

    dp = [INF] * (k + 1)
    dp[0] = 0  # 0 面值付 0 个硬币
    for w, c in zip(values, counts):
        relax(dp[:], dp, w, c, k)  # 松弛前先取快照，同余类内要读"上一轮"的值

    print(dp[k])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
60
61/**
 * 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-05 12:00
 * update_at: 2026-10-05 12:00
 */
// 多重背包恰好凑出 k 的最少硬币数：每种面值一个同余类 + 滑动窗口最小值（单调队列）。

#include <cstdio>

typedef long long ll;

const ll MAXK = 2 * 10 * 1000 + 5; // k <= 2*10^4
const ll INF = 1e9;                // 不可达哨兵（真实答案至多 k，远小于它）

ll n, k;
ll val[205], cnt[205]; // val[i] 第 i 种面值，cnt[i] 该面值的数量上限
ll dp[MAXK];           // dp[v] = 恰好凑出面值 v 的最少硬币数（不可达为 INF）
ll olddp[MAXK];        // 本阶段松弛前的快照：转移只能读上一轮的值
ll que[MAXK];          // 单调队列存同余类内的位置编号 m（0,1,2,...），键 old[r+mw]-m 递增

// 加入面值 w、数量上限 c 的一次有界松弛：把 dp 数组更新为"用前若干种面值"的最优表。
// 按模 w 分同余类，类内第 m 个位置是 v = r + m*w：
//   dp[r+mw] = min_{0<=t<=min(c,m)} ( old[r+(m-t)w] + t )
// 换元 u = m-t 得 dp[r+mw] = m + min_{u in [m-c, m]} ( old[r+uw] - u )，
// 窗口 [m-c, m] 每步右移一格，用单调队列维护键 old[r+uw]-u 的最小值。
void relax_coin(ll w, ll c) {
    if (w > k) return; // 面值超过目标的硬币一枚也用不上，直接跳过这一阶段
    for (ll r = 0; r < w; r++) { // 同余类之间互不干扰，一条一条做
        ll head = 1, tail = 0;   // 队列区间 [head, tail]，空队列 head > tail
        for (ll m = 0; r + m * w <= k; m++) {
            ll pos = r + m * w;
            ll key = olddp[pos] - m; // 候选下标 u=m 的键
            while (head <= tail && olddp[r + que[tail] * w] - que[tail] >= key)
                tail--;              // 队尾键不更小，以后永远轮不到当最小值，弹出
            que[++tail] = m;         // 当前位置入队
            while (m - que[head] > c) // 队首滑出窗口 [m-c, m]，数量上限在这里生效
                head++;
            dp[pos] = m + olddp[r + que[head] * w] - que[head];
        }
    }
}

int main() {
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) scanf("%lld", &val[i]);
    for (ll i = 1; i <= n; i++) scanf("%lld", &cnt[i]);
    scanf("%lld", &k);

    for (ll v = 1; v <= k; v++) dp[v] = INF; // 一开始只有 0 面值可达
    dp[0] = 0;

    for (ll i = 1; i <= n; i++) {
        for (ll v = 0; v <= k; v++) olddp[v] = dp[v]; // 松弛前先取快照
        relax_coin(val[i], cnt[i]);
    }

    printf("%lld\n", dp[k]);
    return 0;
}

复杂度

• 时间复杂度：$O(nk)$。每个面值 $w$ 产生 $w$ 个同余类，类内位置总数 $\leqslant k+1$， 单调队列摊还 $O(1)$ ⇒ 每面值 $O(k)$；最坏 $200 \times 2\times10^4 = 4\times10^6$ 次操作。 面值 $w > k$ 的硬币一枚也用不上，实现直接跳过这一阶段，实际常数更小。 对比朴素 $O(k\sum c_i) \leqslant 8\times10^{10}$、二进制拆分 $\approx 6\times10^7$。
• 空间复杂度：$O(k)$，dp 与快照 old 两个长度 $k+1$ 的数组加单调队列。
• 实测：21 组真实数据全部 PASS，最慢 0.520s、峰值 16.7MB（OJ 限时 1000ms / 128MB； Python 在慢机上仍有 TLE 风险，属允许范围）。

总结

• 多重背包"数量大、容量小"时，逐枚松弛和二进制拆分都把成本压在 $c_i$ 上； 同余类拆分 把内层从"扫全部 $v$"换成"沿一条等差数列滑窗"，成本落到 $O(nk)$。
• 换元 $u = m - t$ 是关键一步：它把"$\min(old + t)$“变成”$\min(old - u) + m$"， 窗口长度与 $m$ 无关，滑动窗口最小值的标准结构才显现出来。
• 单调队列的两句话不变量：队尾淘汰保证队首是最小，队首过期保证最小还活着。 样例表中 $dp[9]=\infty$ 展示了数量上限如何由窗口边界 $[m-c,m]$ 精确表达。
• 贪心在非规范币制下没有最优子结构（$1,3,4$ 凑 6 的反例），必须依赖 DP 的全局性。