GESP 题解库 / 7 级题解 / [GESP202412 七级] 武器购买 · 第 12 / 24 题
GESP202412 七级 · P11377 · 简单

武器购买

选若干武器,使总强度 ≥ P 且总花费 ≤ Q,求最小总花费(无解输出 −1)。

📊
t ≤ 10,n ≤ 100
数据规模
🔢
P, Q ≤ 5 × 10⁴
强度 / 预算上限
⚡
O(nP)
每组时间复杂度
🎯
0/1 背包 + 强度维压缩
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

商店里有 n 个武器,第 i 个武器的强度为 pᵢ、花费为 cᵢ。小杨想买一些武器,使得总强度不小于 P、总花费不超过 Q。

问:是否存在满足条件的方案?如果存在,最少花费是多少?不存在则输出 -1。

输入有多组数据:第一行 t,随后每组给出 n, P, Q 与 n 行 pᵢ, cᵢ。

💡
人话翻译:把"强度"当作背包的下标,把"最少花费"当作 dp 的值。
因为题目只要求"总强度不小于 P",所以超过 P 的部分毫无意义——用 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,且花费最小

需要解决的问题

02
思维导图
整理解题思路的全貌
💰 dp[压缩强度] = 最少花费
🧠 状态
dp[s]:达到压缩强度 s 的最少花费
s 取值 0 … P
超出 P 的一律记在 P 上
答案 = dp[P]
🔁 转移
对每件武器 (pᵢ, cᵢ)
s 从 P 递减到 0(0/1 背包)
dp[min(P, s + pᵢ)] = min(…, dp[s] + cᵢ)
只做"取 min"
🧮 规模账本
状态数 P + 1 ≤ 5 × 10⁴ + 1
每组 O(n · P) ≤ 5 × 10⁶
t ≤ 10 场合计 ≤ 5 × 10⁷
空间只有一个 dp 数组
⚠️ 易错点
强度维正序枚举(武器被重复用)
忘记 min(P, …) 压缩导致越界
只判"不可达",漏判"超预算"
下标与 dp 值的含义弄反
03
样例手算推导
三个样例的完整推演

🧮 样例第 1 组:n = 3, P = 2, Q = 3,武器 (1,2) (1,2) (2,3),答案 3

dp 的初值:dp[0] = 0,dp[1]、dp[2] 都是正无穷(记作 ∞)。每处理一件武器,观察一遍 dp 数组。

处理到武器 (pᵢ, cᵢ)dp[0]dp[1]dp[2]
初始—0∞∞
第 1 件(1, 2)02∞
第 2 件(1, 2)024
第 3 件(2, 3)023
1
第 1 件武器 (p = 1, c = 2)

s = 2:dp[2] 为 ∞,跳过

s = 1:dp[1] 为 ∞,跳过

s = 0:目标 min(2, 0 + 1) = 1,dp[1] = min(∞, 0 + 2) = 2

dp = [0, 2, ∞]

2
第 2 件武器 (p = 1, c = 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]

3
第 3 件武器 (p = 2, c = 3)

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

🔑
手工核对一下三种方案的性价比:只买第 3 件 → 强度 2(够)、花费 3;买前两件 → 强度 2、花费 4;买第 1 + 第 3 件 → 强度 3(也够)、花费 5。
最少花费就是 3——注意"强度超出 P"并不额外加分,所以 dp 只需要记录"至少够不够",这正是压缩维度不会丢信息的原因。

🧮 样例第 2、3 组:两种不同的无解

第 2 组 n = 3, P = 3, Q = 4,武器仍是 (1,2) (1,2) (2,3);第 3 组把 P、Q 放大到 1000。

组号n, P, Q武器最省钱的"够强度"方案dp[P]判定输出
13, 2, 3(1,2) (1,2) (2,3)只买 (2,3):强度 2、花费 333 ≤ 3 ✓3
23, 3, 4(1,2) (1,2) (2,3)买 (1,2) + (2,3):强度 3、花费 555 > 4 ✗ 超预算-1
33, 1000, 1000(1,2) (1,2) (2,3)全部加起来强度也只有 1 + 1 + 2 = 4∞凑不到 P ✗-1
⚠️
两种"无解"要分清:第 2 组是凑得到但买不起(强度能到 3,最省也要 5 元,超过预算 4);第 3 组是压根凑不到(所有武器强度之和 4 < P = 1000,dp[1000] 始终是 ∞)。
代码里判 dp[P] > Q 一次就把两种情况都覆盖了(因为 ∞ > Q 恒成立)——写成"只判是否等于 ∞"就会漏掉第 2 组。
04
解法对比
强度维压缩 DP vs 枚举子集 / 花费维 DP

⚔️ 解法对比

🟢 强度维压缩 0/1 背包(推荐) 推荐

dp[压缩强度] = 最少花费,超出的强度全部压到 P

  • 单组 O(nP) ≤ 5 × 10⁶
  • 空间 O(P),一个数组滚动
  • 代码约 20 行
  • 10 组合计 ≤ 5 × 10⁷
💡
两处关键选择:① 用"强度"做下标(压缩后只有 5 × 10⁴ 格),把"最少花费"存成值;② 用 min(P, s + p) 处理"至少 P"。方向反了(花费做下标)就会多出两个数量级的状态。

🟠 花费维 DP / 枚举子集

用"花费"做下标存最大强度,或直接枚举所有子集

  • 花费最大 5 × 10⁶ → O(n × 5 × 10⁶) = 5 × 10⁸,偏慢
  • 枚举子集是 O(2ⁿ),n = 100 时天文数字
  • 思路直观但不能拿满分
⚠️
为什么要挑小的那一维做下标:DP 的代价是"状态数 × 物品数",所以下标越小越好。强度能被"压到 P",而花费不能(没有上界可利用),这就是选择强度的原因。

📈 性能对比

方案复杂度(单组最坏)可行性
强度维压缩 DPO(nP) ≤ 5 × 10⁶✅ 推荐
花费维 DPO(n × 5 × 10⁶) = 5 × 10⁸⚠️ 偏慢,10 组会超时
枚举所有子集O(2ⁿ),n = 100❌ 不可行
05
算法流程图
每组数据跑一次 0/1 背包
开始读入 t;g = 0g < t 吗?读入这一组的 n、P、Q 与 n 件武器初始化 dp:dp[0] = 0,dp[1..P] = 正无穷取下一件武器 (pᵢ, cᵢ)s 从 P 递减到 0:dp[min(P, s + pᵢ)] = min(…, dp[s] + cᵢ)本组武器都看完了吗?没看完 ✓继续取下一件武器看完了 ✗检查 dp[P]dp[P] ≤ Q 吗?(正无穷也算"否")是 ✓输出最少花费 dp[P]否 ✗输出 -1(凑不够或超预算)g 加 1,还有下一组测试数据吗?结束取下一件武器
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

⚔️ 最少花费是多少

第一行输入一组的 n P Q,随后 n 行输入武器的强度与花费。程序会给出最少花费、还原一份最优方案,并展示 dp 数组的变化。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(强度维压缩 0/1 背包)

#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⁶。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
3 2 3
1 2
1 2
2 3
3 3 4
1 2
1 2
2 3
3 1000 1000
1 2
1 2
2 3
3
-1
-1
题面样例(三组数据)
1
1 1 1
1 1
1恰好够:强度 1 ≥ 1、花费 1 ≤ 1
1
1 5 9
5 10
-1强度够但花费 10 > Q = 9(超预算型无解)
1
2 1 5
1 5
1 3
3两件都够用,选便宜的 3
1
1 3 10
5 2
2单件强度 5 超过 P = 3:验证 min(P, …) 压缩
1
2 50000 50000
50000 50000
1 1
50000P、Q 取最大值且恰好压线通过
✅
自查清单:① 强度维倒序枚举吗?② 有 min(P, s + p) 压缩吗?③ 判 dp[P] > Q 而不是只判"是否为无穷"吗?

🚨 易错点清单

⚠️
强度维正序枚举:会让同一件武器被重复购买,答案偏小。
⚠️
忘记强度压缩:不写 min(P, s + p) 会数组越界。
⚠️
只会判"凑不到":漏掉"凑得到但花费超 Q"这一种无解。
⚠️
下标与值弄反:用花费做下标会多出两个数量级的状态,容易超时。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(nP)
空间复杂度
O(P)
单组运算量
≤ 5 × 10⁶
10 组合计
≤ 5 × 10⁷

时间怎么算的?

空间都用在哪?

只有一个长度 P + 1 的 long long 数组,每组重新申请,空间约 400 KB。

✅ 全部数据合计 5000 万次操作,1 秒限制下轻松通过。关键在于把强度"压缩"到 P,让状态数从 5 × 10⁶ 降到 5 × 10⁴。

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 同时覆盖两种无解边界判定与错误分类
🌟
思考题:如果题目改成"总强度恰好等于 P"(不是"不小于")而且要输出方案,该怎么改?(提示:此时 min(P, s + p) 的压缩会出错——因为"超出"和"恰好"必须区分开,得老老实实开 dp[0..P] 表示"恰好达到",转移写成 dp[s + p] = min(…)(要求 s + p ≤ P),最后判断 dp[P] 是否可达;要输出方案就再记一个前驱数组往回还原。"压缩维度"只对"阈值型(至少/至多)"的问法有效,遇到"恰好"就得还原本来的维度。)