付款方做有限硬币最少张数 DP，找零方做无限硬币最少张数 DP，再枚举实付金额取最优。
OJ: luogu
题目 ID: P2851
难度:提高+/省选-
标签:动态规划多重背包完全背包单调队列背包
日期: 2026-06-20 06:29
题意
要买一件价格为 T 的商品。
- 农夫手里的每种硬币数量有限
- 店家手里的每种硬币数量无限
- 希望“农夫付出的硬币数 + 店家找回的硬币数”最少
要求输出这个最小值。
思路
先看一个可以直接验证想法的小数据暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, target_sum;
int value_input[105], count_input[105];
vector<int> pay_dp, next_dp, change_dp;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> target_sum;
for (int i = 1; i <= n; i++) {
cin >> value_input[i];
}
for (int i = 1; i <= n; i++) {
cin >> count_input[i];
}
int total_sum = 0;
for (int i = 1; i <= n; i++) {
total_sum += value_input[i] * count_input[i];
}
pay_dp.assign(total_sum + 1, INF);
next_dp.assign(total_sum + 1, INF);
pay_dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int s = 0; s <= total_sum; s++) {
next_dp[s] = pay_dp[s];
}
for (int s = 0; s <= total_sum; s++) {
if (pay_dp[s] >= INF) {
continue;
}
// 直接枚举当前面值拿几枚，是最直白的小数据写法。
for (int k = 1; k <= count_input[i]; k++) {
int ns = s + k * value_input[i];
if (ns > total_sum) {
break;
}
next_dp[ns] = min(next_dp[ns], pay_dp[s] + k);
}
}
pay_dp.swap(next_dp);
}
change_dp.assign(total_sum + 1, INF);
change_dp[0] = 0;
for (int i = 1; i <= n; i++) {
int v = value_input[i];
for (int s = v; s <= total_sum; s++) {
change_dp[s] = min(change_dp[s], change_dp[s - v] + 1);
}
}
int answer = INF;
for (int pay = target_sum; pay <= total_sum; pay++) {
if (pay_dp[pay] >= INF || change_dp[pay - target_sum] >= INF) {
continue;
}
answer = min(answer, pay_dp[pay] + change_dp[pay - target_sum]);
}
if (answer >= INF) {
cout << -1 << '\n';
}
else {
cout << answer << '\n';
}
return 0;
}暴力版直接做两件事：
- 用有限硬币 DP 求出“农夫恰好付出
s元时最少要几枚硬币” - 用无限硬币 DP 求出“店家恰好找
d元时最少要几枚硬币”
最后枚举实付金额 s >= T，把两部分加起来取最小值。
这个想法本身就是正解的骨架，真正的问题只在于第一步。
为什么要拆成两个 DP
如果农夫最终付了 s 元，那么店家就必须找：
s - T
于是总硬币数就是：
pay[s] + change[s - T]
其中：
pay[s]：农夫用自己手里有限的硬币，恰好凑出s的最少张数change[d]：店家用无限硬币，恰好找出d的最少张数
第二部分是很标准的完全背包最小值。
难点在第一部分：每种硬币数量有限，而且我们要求的是最少张数，这是一个多重背包最小值问题。
付款方 DP
设：
pay[s]表示恰好凑出s元时，最少要用多少枚自己的硬币
如果当前处理面值 v、数量 c 的硬币，那么转移是：
new[s] = min(old[s - k * v] + k)，其中0 <= k <= c
这就是最朴素的多重背包。
如果直接枚举 k，复杂度会很高。
这里和“多重背包单调队列优化”是同一个套路：按 mod v 的余数分组。
把：
s = q * v + r
代进去，就得到：
new[q * v + r] = min(old[t * v + r] + (q - t))
其中 t 落在一个长度为 c + 1 的滑动窗口里。
于是对每个余数类，只要维护：
old[t * v + r] - t
的窗口最小值，就能把这一层转移优化到线性。
找零方 DP
店家硬币无限，所以是完全背包最小值：
change[d] = min(change[d], change[d - v] + 1)
这一部分很直接。
为什么只需要枚举到 T + Vmax^2
设最大面值是 Vmax。这题的经典结论是：
- 最优方案中，多付的钱不需要超过
Vmax^2
因此只要把农夫实付金额枚举到：
T + Vmax^2
就够了。
在本题里 Vmax <= 120，所以这个范围最多就是：
10000 + 120^2 = 24400
完全可以做 DP。
这也是为什么正解能稳稳落在
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 120;
const int INF = 1e9;
int n, target_sum;
int value_input[105], count_input[105];
int cnt[MAXV + 5];
bool has_value[MAXV + 5];
int limit_sum, max_value;
vector<int> pay_dp, old_dp, change_dp;
vector<int> que;
int score_of(const vector<int> &dp, int pos, int k) {
if (dp[pos] >= INF) {
return INF;
}
return dp[pos] - k;
}
void build_pay_dp() {
pay_dp.assign(limit_sum + 1, INF);
old_dp.assign(limit_sum + 1, INF);
pay_dp[0] = 0;
for (int v = 1; v <= MAXV; v++) {
if (cnt[v] == 0) {
continue;
}
old_dp = pay_dp;
for (int r = 0; r < v; r++) {
int head = 1, tail = 0;
for (int k = 0; k * v + r <= limit_sum; k++) {
int pos = k * v + r;
while (head <= tail && que[head] < k - cnt[v]) {
head++;
}
int cur_score = score_of(old_dp, pos, k);
while (head <= tail) {
int last_k = que[tail];
int last_pos = last_k * v + r;
int last_score = score_of(old_dp, last_pos, last_k);
if (last_score <= cur_score) {
break;
}
tail--;
}
que[++tail] = k;
int best_k = que[head];
int best_pos = best_k * v + r;
if (old_dp[best_pos] >= INF) {
pay_dp[pos] = INF;
}
else {
pay_dp[pos] = old_dp[best_pos] + (k - best_k);
}
}
}
}
}
void build_change_dp() {
int max_extra = limit_sum - target_sum;
change_dp.assign(max_extra + 1, INF);
change_dp[0] = 0;
for (int v = 1; v <= MAXV; v++) {
if (!has_value[v]) {
continue;
}
for (int s = v; s <= max_extra; s++) {
if (change_dp[s - v] + 1 < change_dp[s]) {
change_dp[s] = change_dp[s - v] + 1;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> target_sum;
for (int i = 1; i <= n; i++) {
cin >> value_input[i];
}
for (int i = 1; i <= n; i++) {
cin >> count_input[i];
}
for (int i = 1; i <= MAXV; i++) {
cnt[i] = 0;
has_value[i] = false;
}
max_value = 0;
for (int i = 1; i <= n; i++) {
int v = value_input[i];
cnt[v] += count_input[i];
has_value[v] = true;
if (v > max_value) {
max_value = v;
}
}
// 经典上界：最优方案里，多付的钱不需要超过 max_value^2。
limit_sum = target_sum + max_value * max_value;
que.assign(limit_sum + 5, 0);
build_pay_dp();
build_change_dp();
int answer = INF;
for (int pay = target_sum; pay <= limit_sum; pay++) {
int extra = pay - target_sum;
if (pay_dp[pay] >= INF || change_dp[extra] >= INF) {
continue;
}
answer = min(answer, pay_dp[pay] + change_dp[extra]);
}
if (answer >= INF) {
cout << -1 << '\n';
}
else {
cout << answer << '\n';
}
return 0;
}复杂度
设 W = T + Vmax^2。
- 付款方多重背包单调队列优化：
- 找零方完全背包：
总时间复杂度：
空间复杂度：
总结
这题最关键的不是“怎么找零”，而是先把问题拆开：
- 农夫负责付钱，是有限硬币最少张数
- 店家负责找零，是无限硬币最少张数
拆完以后，真正有技术含量的只剩第一部分的多重背包优化。
所以这题本质上是一个“最小值版的多重背包 + 完全背包拼接题”。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
