[USACO3.1] 邮票 Stamps

题意

有 $n$ 种邮票面值，每种面值都可以使用无限次。

但是一封信最多只能贴 $k$ 张邮票。要求求出最大的正整数 $m$ ，使得 1 到 $m$ 的每个面值都能用不超过 $k$ 张邮票拼出来。

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

原题对象	背包含义
一种邮票面值	一个可以无限使用的物品
使用一张邮票	物品重量增加对应面值
最多 $k$ 张	背包里的“张数”上限
最长连续可达前缀	目标答案

思路

先看最直接的暴力：

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

int k, n;
vector<int> a;
set<int> reachable;

// 暴力枚举最多使用 k 枚邮票时能拼出的所有面值。
// 这个做法只适合小数据，但最容易直接对应题意。
void dfs(int used, int sum) {
    if (used > k) {
        return;
    }

    reachable.insert(sum);
    if (used == k) {
        return;
    }

    for (int v : a) {
        dfs(used + 1, sum + v);
    }
}

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

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

    dfs(0, 0);

    int answer = 0;
    while (reachable.count(answer + 1)) {
        answer++;
    }

    cout << answer << '\n';

    return 0;
}

brute.cpp 直接枚举最多 $k$ 张邮票能拼出的所有面值，再找最长连续前缀。

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

关键观察是：

每种邮票可以无限次使用，所以是完全背包。
我们不需要知道“有多少种拼法”，只需要知道“最少要多少张邮票”。
一旦某个面值需要的邮票数超过 $k$ ，最长连续前缀就断掉了。

于是设：

$dp[x]$ 表示拼出面值 $x$ 需要的最少邮票数

这张表说明状态定义：

状态	含义
$dp[x]$	凑出面值 $x$ 所需的最少邮票数

处理每种邮票面值 $v$ 时：

$dp[x] = min(dp[x], dp[x - v] + 1)$

这是标准的完全背包。

DP 公式

设 $dp_x$ 表示凑出面值 $x$ 所需的最少邮票数。初始化：

dp_0=0,\quad dp_x=+\infty\ (x>0)

对每种邮票面值 $v$ 做完全背包：

dp_x=\min(dp_x,\ dp_{x-v}+1)

最终从 $1$ 开始找到第一个满足 $dp_x>K$ 的面值 $x$ ，答案为：

x-1

公式解释：状态值是凑出某个面值所需的最少邮票数。完全背包转移允许同一种邮票多次使用；从小到大找第一个超过 $K$ 张的面值，它前一个就是连续可表示的最大值。

代码

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

const int INF = 1000000000;

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

    int k, n;
    cin >> k >> n;

    vector<int> a(n);
    int max_a = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        max_a = max(max_a, a[i]);
    }

    int limit = k * max_a;
    vector<int> dp(limit + 1, INF);
    dp[0] = 0;

    // 完全背包：每种面值的邮票可以使用无限次。
    for (int v : a) {
        for (int x = v; x <= limit; x++) {
            dp[x] = min(dp[x], dp[x - v] + 1);
        }
    }

    int answer = 0;
    for (int x = 1; x <= limit; x++) {
        if (dp[x] <= k) {
            answer = x;
        } else {
            break;
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

时间复杂度： $O(n * k * max(a_i))$
空间复杂度： $O(k * max(a_i))$

总结

这题的核心不是“能不能拼出来”，而是“拼出它最少要几张邮票”。

当某个面值的最少张数第一次超过 $k$ 时，最长连续可达前缀就结束了。所以只要把完全背包做到每个面值的最少张数，就能直接扫描答案。

一图流解析

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