: 道具商店)
2025年12月GESP(C++六级): 道具商店
题目描述
道具商店里有n nn件道具可供挑选。第i ii件道具可为玩家提升a i a_iai点攻击力，需要c i c_ici枚金币才能购买，每件道具只能购买一次。现在你有k kk枚金币，请问你最多可以提升多少点攻击力？
输入格式
第一行，两个正整数n , k n,kn,k，表示道具数量以及你所拥有的金币数量。
接下来n nn行，每行两个正整数a i , c i a_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 ≤ 500 1\le k\le 5001≤k≤500，1 ≤ c i ≤ 500 1\le c_i\le 5001≤ci≤500。
对于所有测试点，保证1 ≤ n ≤ 500 1\le n\le 5001≤n≤500，1 ≤ k ≤ 10 9 1 \le k\le 10^91≤k≤109，1 ≤ a i ≤ 500 1\le a_i\le 5001≤ai≤500，1 ≤ c i ≤ 10 9 1\le c_i\le 10^91≤ci≤109。
思路分析
这是一个0-1背包问题的变种，但有一个重要特点：金币k的值可能非常大（最大可达10 9 10^9109），而道具数量n和攻击力a i a_iai的值相对较小（n≤500，a i a_iai≤500）。直接使用传统的基于金币的DP会超时/超内存。
关键洞察
- 总攻击力有限：所有道具的攻击力总和最多为 500×500 = 250,000
- 转换DP状态：由于金币值很大，但攻击力值较小，我们可以将DP状态从"基于金币"转换为"基于攻击力"
- 传统背包：
dp[i][j]= 使用前i个物品，花费j金币能获得的最大攻击力 - 优化转换：
dp[j]= 获得恰好j攻击力所需的最小金币数
- 传统背包：
算法思路
状态定义：
dp[j]：获得恰好j点攻击力所需的最小金币数- 初始时
dp[0] = 0（获得0攻击力需要0金币） - 其他状态初始化为无穷大（表示无法达到）
状态转移：
- 对于每个道具i（攻击力a i a_iai，花费c i c_ici）
- 从总攻击力向下遍历：dp[j] = min(dp[j], dp[j-a i a_iai] +c i c_ici)
- 这表示：要获得j攻击力，可以通过"获得j-a i a_iai攻击力 + 当前道具"来实现
寻找答案：
- 从最大攻击力向下遍历，找到第一个
dp[j] ≤ k的j - 这个j就是能用不超过k金币获得的最大攻击力
- 从最大攻击力向下遍历，找到第一个
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintINF=1e9;// 定义一个足够大的数表示"无穷大"intn,k;// n:道具数量, k:拥有的金币数inta[510],c[510];// a[i]:第i个道具的攻击力, c[i]:第i个道具的价格intdp[250010];// dp[j]:获得恰好j点攻击力所需的最小金币数// 最大攻击力 = 500*500 = 250,000intmain(){// 输入数据cin>>n>>k;intsuma=0;// 所有道具的总攻击力for(inti=1;i<=n;i++){cin>>a[i]>>c[i];suma+=a[i];// 累加总攻击力}// 初始化DP数组// dp[0] = 0 表示获得0攻击力需要0金币// 其他位置初始化为INF（表示无法达到）for(inti=1;i<=suma;i++){dp[i]=INF;}dp[0]=0;// 动态规划：0-1背包问题// 遍历每个道具for(inti=1;i<=n;i++){// 从后往前遍历，避免重复使用同一道具// 遍历所有可能的攻击力值for(intj=suma;j>=a[i];j--){// 状态转移：// 获得j攻击力的最小金币 = min(不使用当前道具, 使用当前道具)// 使用当前道具：需要先获得j-a[i]攻击力，然后花费c[i]金币购买当前道具dp[j]=min(dp[j],dp[j-a[i]]+c[i]);}}// 寻找答案：从最大攻击力开始向下查找// 找到第一个花费不超过k金币的攻击力值intans=0;for(inti=suma;i>=0;i--){if(dp[i]<=k){// 如果获得i攻击力的最小花费不超过kans=i;// 这就是答案break;// 因为是向下遍历，找到的第一个就是最大的}}cout<<ans;// 输出最大攻击力return0;}功能分析
1、关键点：
- 时间复杂度优化：O(n × suma)
- 空间优化：使用一维数组，空间复杂度O(suma)
- 解决了金币值过大的问题：将状态从"基于金币"转换为"基于攻击力"
2、限制条件处理：
- 金币k可能非常大（≤10 9 10^9109）：传统基于金币的DP无法处理
- 攻击力值相对较小：所有道具攻击力总和最多250,000
- 无法达到的攻击力值：用INF表示，确保不会选择
3、算法复杂度
- 时间复杂度：O(n × suma)，其中suma ≤ 250,000
- 空间复杂度：O(suma)，需要存储dp数组
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
