1 条题解
-
0
【本题解由站长编写】
完全背包求每个邮资的最少邮票数: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
- 上传者