T2-12 邮票 Stamps

题意理解

有 $n$ 种邮票，每种面值为 $a_i$，每种数量无限。最多贴 $k$ 张邮票，求最大的 $m$，使得 $1$ 到 $m$ 的所有面值都能凑出。

---

思路分析

这是完全背包的变种。

设 $dp[j]$ 表示凑出面值 $j$ 需要的最少邮票数。如果 $dp[j] \leq k$，则面值 $j$ 可达。

状态转移（完全背包）：

$$dp[j] = \min(dp[j], \, dp[j - a_i] + 1)$$

边界条件：

• $dp[0] = 0$：凑出面值 0 不需要邮票
• 其他初始化为无穷大

答案： 找最大的连续 $m$，使得 $dp[1], dp[2], \cdots, dp[m]$ 都 $\leq k$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 2000005;  // 最大面值 k * max(a) = 200 * 10000
const int INF = 0x3f3f3f3f;

int k, n;        // 邮票上限和种类数
int a[55];       // 每种邮票的面值
int dp[MAXV];    // dp[j]表示凑出面值j需要的最少邮票数

int main() {
    cin >> k >> n;  // 读入邮票上限和种类数
    
    int maxVal = 0;  // 记录最大面值
    for (int i = 1; i <= n; i++) {  // 读入每种邮票的面值
        cin >> a[i];
        maxVal = max(maxVal, a[i]);
    }
    
    int limit = k * maxVal;  // 可能达到的最大面值
    
    memset(dp, 0x3f, sizeof(dp));  // 初始化为无穷大
    dp[0] = 0;  // 边界：凑出面值0不需要邮票
    
    for (int i = 1; i <= n; i++) {  // 枚举每种邮票
        for (int j = a[i]; j <= limit; j++) {  // 完全背包，正序枚举
            dp[j] = min(dp[j], dp[j - a[i]] + 1);  // 状态转移
        }
    }
    
    int ans = 0;  // 答案
    for (int j = 1; j <= limit; j++) {  // 找最大连续可达面值
        if (dp[j] <= k) {  // 面值j可以用不超过k张邮票凑出
            ans = j;
        } else {  // 面值j无法凑出，连续性断了
            break;
        }
    }
    
    cout << ans << endl;  // 输出答案
    return 0;
}