选若干武器,使总强度 ≥ P 且总花费 ≤ Q,求最小总花费(无解输出 −1)。
商店里有 n 个武器,第 i 个武器的强度为 pᵢ、花费为 cᵢ。小杨想买一些武器,使得总强度不小于 P、总花费不超过 Q。
问:是否存在满足条件的方案?如果存在,最少花费是多少?不存在则输出 -1。
输入有多组数据:第一行 t,随后每组给出 n, P, Q 与 n 行 pᵢ, cᵢ。
min(P, s + p) 把所有超额情况压进同一个状态 P,dp 数组就只需要 P + 1 个格子(≤ 5 × 10⁴ + 1)。dp[min(P, s + pᵢ)] = min(…, dp[s] + cᵢ),强度维倒序枚举(0/1 背包,每件武器最多用一次)。dp[P];若它超过 Q(包括"仍是正无穷"=凑不到 P),输出 −1。0/1 背包最小花费强度维压缩倒序枚举无解判定
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 t;每组第一行 n, P, Q;随后 n 行 pᵢ, cᵢ |
| 输出 | 每组一行:最少花费,或 -1 |
| 数据范围 | 1 ≤ t ≤ 10,1 ≤ n ≤ 100 |
| 数值范围 | 1 ≤ pᵢ, cᵢ, P, Q ≤ 5 × 10⁴ |
| 目标 | 总强度 ≥ P、总花费 ≤ Q,且花费最小 |
n × cᵢ ≤ 100 × 5 × 10⁴ = 5 × 10⁶,状态太多;而强度压缩后只有 P + 1 ≤ 5 × 10⁴ + 1 个,用小的一维做下标,代价低得多min(P, s + pᵢ) 把所有 ≥ P 的情况都归到状态 P,于是一句"取 min"就处理完了三种可能:不够(s + p < P)、刚好、超出dp[P] 仍是正无穷);二是凑到了但超预算(dp[P] > Q)。两者都可以用 dp[P] > Q 一并判定dp 的初值:dp[0] = 0,dp[1]、dp[2] 都是正无穷(记作 ∞)。每处理一件武器,观察一遍 dp 数组。
| 处理到 | 武器 (pᵢ, cᵢ) | dp[0] | dp[1] | dp[2] |
|---|---|---|---|---|
| 初始 | — | 0 | ∞ | ∞ |
| 第 1 件 | (1, 2) | 0 | 2 | ∞ |
| 第 2 件 | (1, 2) | 0 | 2 | 4 |
| 第 3 件 | (2, 3) | 0 | 2 | 3 |
s = 2:dp[2] 为 ∞,跳过
s = 1:dp[1] 为 ∞,跳过
s = 0:目标 min(2, 0 + 1) = 1,dp[1] = min(∞, 0 + 2) = 2
dp = [0, 2, ∞]
s = 2:dp[2] 为 ∞,跳过
s = 1:目标 min(2, 2) = 2,dp[2] = min(∞, 2 + 2) = 4
s = 0:目标 min(2, 1) = 1,dp[1] = min(2, 0 + 2) = 2(不变)
dp = [0, 2, 4]
s = 2:目标 min(2, 4) = 2,dp[2] = min(4, 4 + 3) = 4
s = 1:目标 min(2, 3) = 2,dp[2] = min(4, 2 + 3) = 4
s = 0:目标 min(2, 2) = 2,dp[2] = min(4, 0 + 3) = 3
dp[2] = 3
dp[P] = 3 ≤ Q = 3 ✓ 输出 3
第 2 组 n = 3, P = 3, Q = 4,武器仍是 (1,2) (1,2) (2,3);第 3 组把 P、Q 放大到 1000。
| 组号 | n, P, Q | 武器 | 最省钱的"够强度"方案 | dp[P] | 判定 | 输出 |
|---|---|---|---|---|---|---|
| 1 | 3, 2, 3 | (1,2) (1,2) (2,3) | 只买 (2,3):强度 2、花费 3 | 3 | 3 ≤ 3 ✓ | 3 |
| 2 | 3, 3, 4 | (1,2) (1,2) (2,3) | 买 (1,2) + (2,3):强度 3、花费 5 | 5 | 5 > 4 ✗ 超预算 | -1 |
| 3 | 3, 1000, 1000 | (1,2) (1,2) (2,3) | 全部加起来强度也只有 1 + 1 + 2 = 4 | ∞ | 凑不到 P ✗ | -1 |
dp[1000] 始终是 ∞)。dp[P] > Q 一次就把两种情况都覆盖了(因为 ∞ > Q 恒成立)——写成"只判是否等于 ∞"就会漏掉第 2 组。dp[压缩强度] = 最少花费,超出的强度全部压到 P
min(P, s + p) 处理"至少 P"。方向反了(花费做下标)就会多出两个数量级的状态。用"花费"做下标存最大强度,或直接枚举所有子集
| 方案 | 复杂度(单组最坏) | 可行性 |
|---|---|---|
| 强度维压缩 DP | O(nP) ≤ 5 × 10⁶ | ✅ 推荐 |
| 花费维 DP | O(n × 5 × 10⁶) = 5 × 10⁸ | ⚠️ 偏慢,10 组会超时 |
| 枚举所有子集 | O(2ⁿ),n = 100 | ❌ 不可行 |
第一行输入一组的 n P Q,随后 n 行输入武器的强度与花费。程序会给出最少花费、还原一份最优方案,并展示 dp 数组的变化。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const long long INF = (long long)4e18; int main() { int t; scanf("%d", &t); while (t--) { int n, P, Q; scanf("%d %d %d", &n, &P, &Q); vector<long long> dp(P + 1, INF); dp[0] = 0; // 0 强度、0 花费 for (int i = 0; i < n; i++) { int p, c; scanf("%d %d", &p, &c); for (int s = P; s >= 0; s--) { // 倒序:每件武器只用一次 if (dp[s] == INF) continue; int tgt = min(P, s + p); // 强度压缩:>= P 都记在 P 上 dp[tgt] = min(dp[tgt], dp[s] + c); } } if (dp[P] > Q) printf("-1\n"); // 同时覆盖"凑不到"与"超预算" else printf("%lld\n", dp[P]); } return 0; }
dp[P] > Q 能一句话判掉两种无解?因为若强度根本凑不到 P,dp[P] 会一直保持 INF = 4 × 10¹⁸,它自然也大于任何 Q。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
vector<long long> dp(P + 1, INF); dp[0] = 0; | 状态定义 | 下标 = 压缩强度,值 = 最少花费;花 0 元拿 0 强度 |
for (int s = P; s >= 0; s--) | 枚举顺序 | 倒序保证每件武器最多用一次(0/1 背包) |
int tgt = min(P, s + p); | 强度压缩 | "至少 P" ⟹ 超额部分全部归到状态 P |
dp[tgt] = min(dp[tgt], dp[s] + c); | 转移 | 取更小的花费(求最小,不是求最大) |
if (dp[P] > Q) printf("-1\n"); | 答案判定 | 一次判掉"凑不到"和"超预算"两种无解 |
min(P, …) 压缩,dp[s + p] 会越界(s + p 可超过 P);③ 只判"是否等于 INF",漏掉"凑得到但花费 > Q";④ 把下标和值的含义弄反(用花费做下标、存最大强度),状态数会暴涨到 5 × 10⁶。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 3 -1 -1 | 题面样例(三组数据) |
1 | 1 | 恰好够:强度 1 ≥ 1、花费 1 ≤ 1 |
1 | -1 | 强度够但花费 10 > Q = 9(超预算型无解) |
1 | 3 | 两件都够用,选便宜的 3 |
1 | 2 | 单件强度 5 超过 P = 3:验证 min(P, …) 压缩 |
1 | 50000 | P、Q 取最大值且恰好压线通过 |
min(P, s + p) 压缩吗?③ 判 dp[P] > Q 而不是只判"是否为无穷"吗?min(P, s + p) 会数组越界。只有一个长度 P + 1 的 long long 数组,每组重新申请,空间约 400 KB。
✅ 全部数据合计 5000 万次操作,1 秒限制下轻松通过。关键在于把强度"压缩"到 P,让状态数从 5 × 10⁶ 降到 5 × 10⁴。
// 0/1 背包:求"达到某强度所需的最小花费" vector<long long> dp(P + 1, INF); dp[0] = 0; for (int i = 0; i < n; i++) { int p, c; scanf("%d %d", &p, &c); for (int s = P; s >= 0; s--) { // 倒序 = 每件最多用一次 if (dp[s] == INF) continue; int tgt = min(P, s + p); // "至少 P" 的维度压缩 dp[tgt] = min(dp[tgt], dp[s] + c); } } // 答案:dp[P] > Q ? -1 : dp[P] // 对照三种常见问法: // 1) 总强度“不超过 P”的最大强度 → 普通 0/1 背包:dp2[s] = max(dp2[s], dp2[s-p]+p) // 2) “至少 P”的最小花费 → 本题:min(P, s+p) 压缩 + 取 min // 3) “恰好等于 P” → 不能压缩,必须开满容量并判 dp[P] 是否可达 // 若每种武器可以买无限件(完全背包):把 s 的枚举改成从 0 到 P 正序即可 // 若要求输出方案:额外记 par[目标] = (来源状态, 物品编号),最后从 P 往回走
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 0/1 背包 | 倒序枚举容量维 | 每件最多选一次的选择类问题 |
| 维度压缩 | min(P, s + p) 把超额归并 | "至少/不少于"的阈值问题 |
| 下标选小的那一维 | 用强度(5 × 10⁴)而非花费(5 × 10⁶) | 复杂度取舍与状态设计 |
| 统一的答案判定 | dp[P] > Q 同时覆盖两种无解 | 边界判定与错误分类 |
dp[0..P] 表示"恰好达到",转移写成 dp[s + p] = min(…)(要求 s + p ≤ P),最后判断 dp[P] 是否可达;要输出方案就再记一个前驱数组往回还原。"压缩维度"只对"阈值型(至少/至多)"的问法有效,遇到"恰好"就得还原本来的维度。)