跳至正文

1 条题解

  • 0
    @ 2026-10-7 23:29:54

    【本题解由站长编写】

    完全背包求每个邮资的最少邮票数:dp[s] = 凑出邮资 s 的最少张数(每种面值无限张但总张数受 N 限制,最小张数天然满足)。从 1 开始连续扫描,dp[s] ≤ N 就继续,否则前一格就是答案;没有 1 分面值时 dp[1] 必然超限输出 0。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        int N, M;
        cin >> N >> M;
        vector<int> x(M);
        for (auto &v : x) cin >> v;
        const int CAP = 25500;
        vector<int> dp(CAP + 1, 1e9);
        dp[0] = 0;
        for (int s = 1; s <= CAP; s++)
            for (int v : x)
                if (s >= v && dp[s - v] + 1 < dp[s]) dp[s] = dp[s - v] + 1;
        int ans = 0;
        for (int s = 1; s <= CAP && dp[s] <= N; s++) ans = s;
        cout << ans << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4318
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者