武器购买 题解

一、题目分析

小杨要从 $n$ 个武器中选出若干件，每个武器有强度 $p_i$ 和花费 $c_i$。要求选出的武器总强度不小于 $P$，总花费不超过 $Q$。如果在这样的前提下能够选出武器，输出最小的总花费；如果没有任何合法方案，输出 -1。

本题数据范围：$t \le 10$，$n \le 100$，$p_i, c_i, P, Q \le 5\times 10^4$。题目的本质是在满足背包容量限制的前提下，让总价值达到某一阈值，并希望最小化容量的使用。是一个标准的 0-1 背包变种问题。

二、解题思路

常规的 0-1 背包问题通常是在容量限制下最大化价值。而本题稍有不同：

• 我们将总花费看作背包的“容量”，总容量上限为 $Q$。
• 我们将总强度看作背包的“价值”，希望在达到一定价值（$P$）时，消耗的容量最少。

因此可以设 $dp[j]$ 表示总花费恰好为 $j$ 时，能获得的最大总强度。初始化 $dp[0] = 0$，其它状态置为负无穷，表示不可达。

对于每一个武器 $(p_i, c_i)$，我们按照 0-1 背包的逆序方式进行转移：

意思是在已花费 $j-c_i$ 的基础上，加上当前武器，可以将总强度提高 $p_i$。

处理完所有武器后，我们只需要从小到大遍历 $j \in [0, Q]$，找到第一个满足 $dp[j] \ge P$ 的 $j$，这个 $j$ 就是满足条件的最小花费。如果遍历完都没有找到，说明无解，输出 -1。

三、算法说明

1. 状态定义
   $dp[j]$：花费恰好为 $j$ 时能获得的最大总强度。
   取值范围 $j = 0 \sim Q$。
   初始值：$dp[0] = 0$，其他 $dp[j] = -\infty$。

2. 状态转移
   对于每个武器 $(p, c)$，倒序枚举 $j$ 从 $Q$ 到 $c$：

   • 如果 $dp[j-c]$ 是可达状态（代码中用 dp[j-c] >= 0 判断），则可以尝试转移：
     $$dp[j]=\max (dp[j],dp[j-c]+p)$$
   • 由于强度 $p$ 均为正整数，只有从可达状态转移来的 $dp$ 值才会非负，因此 dp[j-c] >= 0 能很好地判断状态是否可达。严格的判断也可以用 dp[j-c] != -inf。

3. 答案提取
   遍历 $j = 0, 1, \dots, Q$，找到第一个满足 $dp[j] \ge P$ 的 $j$ 作为答案。若不存在，返回 -1。

4. 边界情况

   • 当 $Q=0$ 时，只能不买任何武器。若 $P \le 0$（题目中 $P\ge 1$），则答案为 $0$，否则无解。实际数据 $P\ge 1$，所以 $Q=0$ 时必然无解。
   • 强度或花费可能较大，但用 long long 足够存储。

四、时间复杂度分析

对于每组测试数据，算法进行了两层循环：

• 外层循环：遍历 $n$ 个武器，$n \le 100$。
• 内层循环：倒序枚举 $j$ 从 $Q$ 到 $c_i$，$Q \le 5\times 10^4$。

因此，单组数据时间复杂度为 $O(n \times Q)$，最大计算量约为 $100 \times 5\times 10^4 = 5\times 10^6$。
共有 $t \le 10$ 组，总计算量约为 $5\times 10^7$，在时间限制 1000ms 内使用 C++ 可以轻松通过。

空间复杂度为 $O(Q)$，即 $50010$ 个 long long，完全在 512MB 内存限制内。

五、参考代码与详解

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4#define ll long long
5
6ll dp[50010];  // dp[j] 表示总花费恰好为 j 时的最大总强度
7
8ll solve(int n, int P, int Q, vector<pair<int, int>>& weapons) {
9    dp[0] = 0;                       // 不买任何武器时，花费0，强度0
10    for (auto& weapon : weapons) {   // 依次考虑每个武器
11        int p = weapon.first;        // 强度
12        int c = weapon.second;       // 花费
13        for (int j = Q; j >= c; --j) {  // 0-1背包倒序遍历
14            if (dp[j - c] >= 0) {      // 如果状态 j-c 可达
15                dp[j] = max(dp[j], dp[j - c] + p);  // 尝试更新
16            }
17        }
18    }
19    for (int j = 0; j <= Q; ++j) {   // 寻找最小花费
20        if (dp[j] >= P) {            // 达到强度要求
21            return j;
22        }
23    }
24    return -1;                       // 无解
25}
26
27int main() {
28    int t;
29    cin >> t;
30    while (t--) {
31        int n, P, Q;
32        cin >> n >> P >> Q;
33        memset(dp, -0x3f, sizeof dp); // 初始化为负无穷，表示不可达
34        vector<pair<int, int>> weapons(n);
35        for (int i = 0; i < n; ++i) {
36            cin >> weapons[i].first >> weapons[i].second;
37        }
38        cout << solve(n, P, Q, weapons) << "\n";
39    }
40    return 0;
41}

代码细节说明

• memset(dp, -0x3f, sizeof dp)：将 dp 数组每个字节设为 0x3f 取负后的值，用于表示负无穷。因为强度为正，正常的 $dp$ 值都会大于等于 $0$，所以用 dp[j] >= 0 就能判断状态是否可达。
• dp[0] = 0：购买零件武器，花费为 $0$ 且强度为 $0$，这是唯一的初始合法状态。
• 内层循环中使用 if (dp[j - c] >= 0)：该条件等价于“前一个状态是可达的”。由于所有强度 $p_i \ge 1$，经过转移的 $dp$ 值必然是正数，只有初始的 $dp[0] = 0$ 是零值。因此 >= 0 的判断既简洁又正确。
• 最后从小到大检查 $dp[j]$，一经发现满足条件立刻返回 $j$，保证了最小花费的要求。