企业官网建设流程全解析

中国建设银行密码重置网站,如何自己创网站,域名空间网站推广,重庆网站关键词推广2025年12月GESP(C六级): 道具商店 题目描述 道具商店里有 n n n 件道具可供挑选。第 i i i 件道具可为玩家提升 a i a_i ai​ 点攻击力#xff0c;需要 c i c_i ci​ 枚金币才能购买#xff0c;每件道具只能购买一次。现在你有 k k k 枚金币#xff0c;请问你最多可以…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输入 13 5 99 1 33 2 11 3输出 1132输入输出样例 2输入 24 100 10 1 20 11 40 33 100 99输出 2110说明/提示对于60 % 60\%60%的测试点保证1 ≤ k ≤ 500 1\le k\le 5001≤k≤5001 ≤ c i ≤ 500 1\le c_i\le 5001≤ci​≤500。对于所有测试点保证1 ≤ n ≤ 500 1\le n\le 5001≤n≤5001 ≤ k ≤ 10 9 1 \le k\le 10^91≤k≤1091 ≤ a i ≤ 500 1\le a_i\le 5001≤ai​≤5001 ≤ 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≤500a 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金币获得的最大攻击力代码实现#includebits/stdc.husingnamespacestd;constintINF1e9;// 定义一个足够大的数表示无穷大intn,k;// n:道具数量, k:拥有的金币数inta[510],c[510];// a[i]:第i个道具的攻击力, c[i]:第i个道具的价格intdp[250010];// dp[j]:获得恰好j点攻击力所需的最小金币数// 最大攻击力 500*500 250,000intmain(){// 输入数据cinnk;intsuma0;// 所有道具的总攻击力for(inti1;in;i){cina[i]c[i];sumaa[i];// 累加总攻击力}// 初始化DP数组// dp[0] 0 表示获得0攻击力需要0金币// 其他位置初始化为INF表示无法达到for(inti1;isuma;i){dp[i]INF;}dp[0]0;// 动态规划0-1背包问题// 遍历每个道具for(inti1;in;i){// 从后往前遍历避免重复使用同一道具// 遍历所有可能的攻击力值for(intjsuma;ja[i];j--){// 状态转移// 获得j攻击力的最小金币 min(不使用当前道具, 使用当前道具)// 使用当前道具需要先获得j-a[i]攻击力然后花费c[i]金币购买当前道具dp[j]min(dp[j],dp[j-a[i]]c[i]);}}// 寻找答案从最大攻击力开始向下查找// 找到第一个花费不超过k金币的攻击力值intans0;for(intisuma;i0;i--){if(dp[i]k){// 如果获得i攻击力的最小花费不超过kansi;// 这就是答案break;// 因为是向下遍历找到的第一个就是最大的}}coutans;// 输出最大攻击力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数组各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}