13024.道具商店

题目分析

你有 $n$ 件道具，每件道具有一个攻击力 $a_i$ 和一个价格 $c_i$，每件只能买一次。你有 $k$ 枚金币，问最多能获得多少攻击力。

这是一个典型的 0/1 背包 问题：

• 背包容量：金币数 $k$
• 物品重量：价格 $c_i$
• 物品价值：攻击力 $a_i$

常规做法是用 f[j] 表示花费 $j$ 枚金币能获得的最大攻击力，复杂度为 $O(n \cdot k)$。
但本题中 $k$ 可以达到 $10^9$，直接做背包会超时，而且数组也开不下。

注意到另一个维度——攻击力 $a_i$ 很小（$a_i \le 500$），总攻击力的上限是 $n \times 500 = 250000$ 左右，这个范围是完全可以接受的。因此我们可以交换 DP 的状态与值，将攻击力作为状态，金币作为值。

解题思路

定义 f[x] 表示：获得攻击力 $x$ 所需的最小金币数。

• 初始化：f[0] = 0，其余 f[x] 设为一个充分大的数（如 $10^9+10$）。

• 对于每一件道具 $(a_i, c_i)$，我们做一次 0/1 背包：

  从大到小枚举攻击力 $j$，用已获得 $j-a_i$ 攻击力的最小花费加上 $c_i$ 来更新 f[j]：

  f[j] = min(f[j], f[j - a_i] + c_i)
  

• 最终答案就是满足 f[x] <= k 的最大的 $x$。

这样做的时间复杂度是 $O(n \cdot S)$，其中 $S = \sum a_i \approx 250000$，在 $n \le 500$ 时运算量大约在 $1.25 \times 10^8$，在 C++ 中是可以接受的。

算法说明

1. 状态定义

设 f[i] 表示恰好获得攻击力 $i$ 所需要的最小金币数。
如果不能达到攻击力 $i$，则值为无穷大。

2. 状态转移

对于每个道具 $(a, c)$，我们倒序枚举当前总攻击力 $j$（从已有的最大可能攻击力降到 $a$）：

cpp
复制
1for (int j = s; j >= a; j--)
2    f[j] = min(f[j], f[j - a] + c);

其中 s 是当前已经处理过的道具的攻击力总和，这样可以进一步缩小枚举范围，提高效率。

3. 初始化

• f[0] = 0：获得 0 攻击力不需要金币。
• 其他所有 f[i] 初始化为一个大于可能最大花费的数，本题中 1e9 + 10 足够。

4. 最终答案

遍历所有可能的攻击力 $i$，如果 f[i] <= k，则 $i$ 是可以达到的，取最大值即可。

时间复杂度分析

• 每件道具处理时，枚举的攻击力范围不超过当前已处理道具的总攻击力 $S = \sum_{i=1}^{n} a_i$。

• 最坏情况下 $S \approx 500 \times 500 = 250000$，因此总时间复杂度为：
  [
  O(n \cdot S) = O(500 \times 250000) = O(1.25 \times 10^8)
  ]
  在 1000ms 的时间限制内，C++ 可以通过。

• 空间复杂度：$O(S)$，只需要一个一维数组即可。

参考代码解释

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4const int N = 505;
5const int oo = 1e9 + 10;
6int n, k;
7int f[N * N];
8
9int main() {
10    scanf("%d%d", &n, &k);
11    // 初始化 f 数组：0 攻击力花费 0，其余设为无穷大
12    for (int i = 1; i < N * N; i++)
13        f[i] = oo;
14    int s = 0;  // 记录已经处理过的道具的攻击力总和
15    for (int i = 1; i <= n; i++) {
16        int a, c;
17        scanf("%d%d", &a, &c);
18        s += a;  // 更新当前可能的最大攻击力
19        // 0/1 背包：倒序更新
20        for (int j = s; j >= a; j--)
21            f[j] = min(f[j], f[j - a] + c);
22    }
23    int ans = 0;
24    // 找到花费不超过 k 的最大攻击力
25    for (int i = 0; i < N * N; i++)
26        if (f[i] <= k)
27            ans = i;
28    printf("%d\n", ans);
29    return 0;
30}

代码要点说明：

• N * N 是 505 * 505 = 255025，略大于最大总攻击力 250000，保证数组不会越界。
• s 变量记录了当前所有已处理道具的总攻击力，每次更新时从 s 开始倒序枚举，避免不必要的计算。
• 最终遍历 f 数组时，所有花费不超过 $k$ 的攻击力都是合法的，取下标最大值即为答案。

本题通过交换 DP 状态与值的技巧，成功将不可行的 $O(nk)$ 算法优化为 $O(n \cdot \sum a_i)$，解决了容量过大而价值较小的特殊背包问题。