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 1
20 11
40 33
100 99

输出 #2

110

说明/提示

对于 $60\%$ 的测试点，保证 $1\le k\le 500$，$1\le c_i\le 500$。

对于所有测试点，保证 $1\le n\le 500$，$1\le k\le 10^9$，$1\le a_i\le 500$，$1\le c_i\le 10^9$。

【题解】P14920 [GESP202512 六级] 道具商店

这道题是一道典型的变形01背包问题，常规的01背包思路会因为金币容量 k 过大（最大 $10^9$）而无法直接实现，因此需要转换思考维度来解决。

题目核心思路分析

常规01背包会定义 dp[j] 为“花费 j 金币能获得的最大攻击力”，但本题中 k 高达 $10^9$，无法开这么大的数组。观察数据范围发现：

• 每件道具的攻击力 $a_i\le 500$，道具数量 $n\le 500$，因此所有道具的总攻击力最大为 $500\times 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[250005];  // dp[j]：获得j点攻击力需要的最少金币数，最大攻击力总和为500*500=250000
int sum=0;      // 所有道具的攻击力总和，作为dp遍历的上界
int ans=0;      // 最终答案：最多能提升的攻击力

int main(){
    // 输入道具数量和金币数
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>c[i];
        sum+=a[i];  // 累加所有道具的攻击力，得到最大可能的攻击力总和
    }
    
    // 初始化dp数组：除了dp[0]（0攻击力需要0金币），其余初始化为极大值（表示不可达）
    // 1e18远大于题目中k的最大值1e9，能有效区分“可达”和“不可达”
    for(int i=1;i<=sum;i++){
        dp[i]=1e18;
    }
    
    // 01背包核心循环：遍历每件道具
    for (int i=1;i<=n;i++){
        // 逆序遍历攻击力（01背包经典操作，避免同一道具被重复选取）
        for(int j=sum;j>=a[i];j--){
            // 状态转移：
            // 获得j点攻击力的最小金币数 = min(不选当前道具的原值, 选当前道具的成本)
            // 选当前道具的成本 = 获得j-a[i]点攻击力的最小金币数 + 当前道具的成本c[i]
            dp[j]=min(dp[j],dp[j-a[i]]+c[i]);
        }
    }
    
    // 遍历所有可能的攻击力值，找到花费≤k的最大攻击力
    for(int i=1;i<=sum;i++){
        if (dp[i]<=k) ans=i;  // 只要当前攻击力可达，就更新答案
    }
    
    // 输出最终结果
    cout<<ans;
	return 0;
}

总结

1. 维度转换：将背包的“容量维度”从金币换成攻击力，解决了金币数值过大无法开数组的问题。
2. 状态定义：dp[j] 表示获得 j 攻击力的最小金币消耗，是本题的核心创新点。
3. 01背包规则：逆序遍历攻击力保证每件道具仅被选取一次，符合“每件道具只能买一次”的题目要求。
4. 答案查找：遍历所有可能的攻击力值，筛选出“花费≤k”的最大值，即为最终答案。

这道题的关键在于观察数据范围的特点，跳出常规背包的思维定式，通过维度转换将不可解的问题转化为可解的常规01背包问题。