CCF-GESP计算机学会等级考试2025年12月六级C++T2 道具商店

P14920 [GESP202512 六级] 道具商店

题目描述

道具商店里有 nnn 件道具可供挑选。第 iii 件道具可为玩家提升 aia_iai​ 点攻击力，需要 cic_ici​ 枚金币才能购买，每件道具只能购买一次。现在你有 kkk 枚金币，请问你最多可以提升多少点攻击力？

输入格式

第一行，两个正整数 n,kn,kn,k，表示道具数量以及你所拥有的金币数量。

接下来 nnn 行，每行两个正整数 ai,cia_i,c_iai​,ci​，表示道具所提升的攻击力点数，以及购买所需的金币数量。

输出格式

输出一行，一个整数，表示最多可以提升的攻击力点数。

输入输出样例 #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%60\%60% 的测试点，保证 1≤k≤5001\le k\le 5001≤k≤500，1≤ci≤5001\le c_i\le 5001≤ci​≤500。

对于所有测试点，保证 1≤n≤5001\le n\le 5001≤n≤500，1≤k≤1091 \le k\le 10^91≤k≤109，1≤ai≤5001\le a_i\le 5001≤ai​≤500，1≤ci≤1091\le c_i\le 10^91≤ci​≤109。

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

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

题目核心思路分析

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

• 每件道具的攻击力 ai≤500a_i \le 500ai​≤500，道具数量 n≤500n \le 500n≤500，因此所有道具的总攻击力最大为 500×500=250000500 \times 500 = 250000500×500=250000（这个数值很小，完全可以用数组存储）。

因此我们转换背包维度：定义 dp[j] 为“获得 j 点攻击力所需的最少金币数”。通过这个转换，我们只需要处理 j 从 0 到 250000 的情况，最后遍历所有可能的攻击力值，找到满足 dp[j] ≤ k 的最大 j 即可。

#include<bits/stdc++.h>usingnamespace std;int n,k;// n：道具数量，k：拥有的金币总数int a[505];// a[i]：第i件道具能提升的攻击力int c[505];// c[i]：第i件道具的购买成本（需要的金币数）longlong dp[250005];// dp[j]：获得j点攻击力需要的最少金币数，最大攻击力总和为500*500=250000int sum=0;// 所有道具的攻击力总和，作为dp遍历的上界int ans=0;// 最终答案：最多能提升的攻击力intmain(){// 输入道具数量和金币数 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;return0;}

总结

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

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