P14920 [GESP202512 六级] 道具商店
题目描述
道具商店里有 n 件道具可供挑选。第 i 件道具可为玩家提升 a_i 点攻击力，需要 c_i 枚金币才能购买，每件道具只能购买一次。现在你有 k 枚金币，请问你最多可以提升多少点攻击力？
输入格式
第一行，两个正整数 n, k，表示道具数量以及你所拥有的金币数量。
接下来 n 行，每行两个正整数 a_i, c_i，表示道具所提升的攻击力点数，以及购买所需的金币数量。
输出格式
输出一行，一个整数，表示最多可以提升的攻击力点数。
输入输出样例 #1
输入 #1
3 5
99 1
33 2
11 3
输出 #1
132
输入输出样例 #2
输入 #2
4 100
10 10
1 20
11 40
33 100
99
输出 #2
110
说明/提示
对于 60% 的测试点，保证 1≤k≤500，1≤c_i≤500。
对于所有测试点，保证 1≤n≤500，1≤k≤10^9，1≤a_i≤500，1≤c_i≤10^9。
【题解】P14920 [GESP202512 六级] 道具商店
这道题是一道典型的变形 01 背包问题。常规的 01 背包思路会因为金币容量 k 过大（最大 10^9）而无法直接实现，因此需要转换思考维度来解决。
题目核心思路分析
常规 01 背包会定义 dp[j] 为'花费 j 金币能获得的最大攻击力'，但本题中 k 高达 10^9，无法开这么大的数组。观察数据范围发现：
- 每件道具的攻击力 a_i ≤ 500，道具数量 n ≤ 500，因此所有道具的总攻击力最大为 500 × 500 = 250000（这个数值很小，完全可以用数组存储）。
因此我们转换背包维度：定义 dp[j] 为'获得 j 点攻击力所需的最少金币数'。通过这个转换，我们只需要处理 j 从 0 到 250000 的情况，最后遍历所有可能的攻击力值，找到满足 dp[j] ≤ k 的最大 j 即可。
#include<bits/stdc++.h>
using namespace std;
int n, k; // n：道具数量，k：拥有的金币总数
int a[505]; // a[i]：第 i 件道具能提升的攻击力
int c[505]; // c[i]：第 i 件道具的购买成本（需要的金币数）
long long dp[];
sum = ;
ans = ;
{
cin >> n >> k;
( i = ; i <= n; i++) {
cin >> a[i] >> c[i];
sum += a[i];
}
( i = ; i <= sum; i++) {
dp[i] = ;
}
( i = ; i <= n; i++) {
( j = sum; j >= a[i]; j--) {
dp[j] = (dp[j], dp[j - a[i]] + c[i]);
}
}
( i = ; i <= sum; i++) {
(dp[i] <= k) ans = i;
}
cout << ans;
;
}
