记录132#includebits/stdc.h // 引入C万能头文件包含所有常用的标准库 using namespace std; // 使用标准命名空间std #define ll long long // 定义长整型别名ll因为金币数量最大为1e9累加容易溢出int const int MAX_SUM250005; // 定义常量表示所有道具攻击力总和的最大值(500*500) const ll INF1e18; // 定义一个极大的数作为无穷大表示某种攻击力无法达到 int n; // 定义变量n表示道具的总数量 ll k; // 定义变量k表示玩家拥有的金币总数预算上限 int a[505],c[505]; // 定义数组a[i]表示第i件道具的攻击力c[i]表示购买所需的金币 ll dp[MAX_SUM]; // 定义dp数组dp[j]表示获得j点攻击力所需要的最少金币数 int total_a0; // 定义变量total_a用来累加所有道具的攻击力总和 int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭标准流同步提升输入输出效率 cin.tie(0); // 解除cin与cout的绑定加快读取速度 cinnk; // 读入道具数量和金币总数 for(int i1;in;i){ // 循环读入每件道具的信息 cina[i]c[i]; // 读入第i件道具的攻击力和花费 total_aa[i]; // 累加攻击力总和作为dp数组的遍历上界 } // 初始化dp数组除了0点攻击力花费0金币外其余状态都初始化为无穷大表示不可达 for(int i0;itotal_a;i){ dp[i]INF; } dp[0]0; // 获得0点攻击力不需要花费任何金币 // 01背包核心循环遍历每一件道具 for(int i1;in;i){ // 逆序遍历攻击力从大到小这是01背包一维数组优化的经典操作防止同一件道具被重复选取 for(int jtotal_a;ja[i];j--){ // 状态转移方程取“不买当前道具”和“买当前道具”两者中花费金币较少的方案 dp[j]min(dp[j],dp[j-a[i]]c[i]); } } int ans0; // 定义变量ans用来记录最终的最大攻击力 // 遍历所有可能的攻击力找到花费在预算k以内的最大攻击力 for(int j0;jtotal_a;j){ if(dp[j]k){ // 如果获得j点攻击力的最小花费不超过拥有的金币数 ansmax(ans,j); // 更新最大攻击力 } } coutans\n; // 输出最多可以提升的攻击力点数 return 0; // 程序正常结束 }题目传送门https://www.luogu.com.cn/problem/P14920前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道经典的01背包问题的变种。常规思路的瓶颈在标准的背包问题中我们通常定义dp[j]为“花费 j 枚金币能获得的最大攻击力”。但是本题中金币数量k和道具花费c_i最大可达 10^9如果以金币作为背包容量数组根本开不下时间复杂度也会严重超标。逆向思维交换价值与代价观察数据范围道具数量n最大只有 500每件道具的攻击力a_i最大只有 500。这意味着所有道具的攻击力总和最大仅为 500 × 500 250000。因此我们可以将“代价”和“价值”互换定义dp[j]为“获得j点攻击力所需要的最少金币数”。这样背包的容量就变成了攻击力总和约 2.5 × 10^5完全在可接受的范围内。状态转移与答案提取状态转移方程为dp[j] min(dp[j], dp[j - a_i] c_i)。在计算出所有攻击力对应的最小花费后我们只需要从大到小或遍历所有寻找满足dp[j] ≤ k花费在预算内的最大的j即为最终答案。代码分块详细解释1. 头文件、常量与全局变量定义#includebits/stdc.h using namespace std; #define ll long long // 定义长整型别名 ll因为金币数量最大为 1e9累加容易溢出 int const int MAX_SUM250005; // 定义常量表示所有道具攻击力总和的最大值 (500*500) const ll INF1e18; // 定义一个极大的数作为无穷大表示某种攻击力无法达到 int n; // 定义变量 n表示道具的总数量 ll k; // 定义变量 k表示玩家拥有的金币总数预算上限 int a[505], c[505]; // 定义数组a[i] 表示第 i 件道具的攻击力c[i] 表示购买所需的金币 ll dp[MAX_SUM]; // 定义 dp 数组dp[j] 表示获得 j 点攻击力所需要的最少金币数 int total_a0; // 定义变量 total_a用来累加所有道具的攻击力总和详细分析这部分奠定了算法的基础。由于金币花费可能达到 109累加后极易超出int范围因此金币相关变量和dp数组必须使用long long。INF被设置为 1018用于初始化dp数组代表“当前攻击力暂时无法达到”的状态。MAX_SUM的设定非常巧妙它利用了题目中a_i和n较小的约束将背包容量压缩到了 2.5 × 105 级别。2. 输入处理与数据准备int main(){ ios::sync_with_stdio(false); // 关闭标准流同步提升输入输出效率 cin.tie(0); // 解除 cin 与 cout 的绑定加快读取速度 cinnk; // 读入道具数量和金币总数 for(int i1;in;i){ // 循环读入每件道具的信息 cina[i]c[i]; // 读入第 i 件道具的攻击力和花费 total_aa[i]; // 累加攻击力总和作为 dp 数组的遍历上界 }详细分析在读取数据的同时程序计算了所有道具的攻击力总和total_a。这个变量至关重要它决定了后续dp数组需要遍历的确切范围避免了无意义的循环进一步提升了程序的运行效率。3. DP 数组初始化// 初始化 dp 数组除了 0 点攻击力花费 0 金币外其余状态都初始化为无穷大表示不可达 for(int i0;itotal_a;i){ dp[i]INF; } dp[0]0; // 获得 0 点攻击力不需要花费任何金币详细分析这是一个标准的“求最小值”型 DP 的初始化操作。将状态初始化为无穷大是为了在后续的状态转移方程min()中能够正确地筛选出真正的最小花费。dp[0] 0则是动态规划的基准状态。4. 01 背包核心循环// 01背包核心循环遍历每一件道具 for(int i1;in;i){ // 逆序遍历攻击力从大到小这是 01背包一维数组优化的经典操作防止同一件道具被重复选取 for(int jtotal_a;ja[i];j--){ // 状态转移方程取“不买当前道具”和“买当前道具”两者中花费金币较少的方案 dp[j]min(dp[j],dp[j-a[i]]c[i]); } }详细分析这是算法的灵魂。逆序遍历的必要性因为每件道具只能购买一次01背包在更新dp[j]时我们需要依赖上一轮未购买当前道具时的dp[j - a_i]的状态。如果正序遍历dp[j - a_i]会在当前轮次被提前更新导致同一件道具被多次购买这就变成了完全背包。逆序遍历完美规避了这个问题。状态转移dp[j - a_i] c_i表示为了凑出j点攻击力我们选择购买第i件道具那么就需要在凑出j - a_i点攻击力的最小花费基础上再加上当前道具的花费c_i。5. 提取答案与输出int ans0; // 定义变量 ans用来记录最终的最大攻击力 // 遍历所有可能的攻击力找到花费在预算 k 以内的最大攻击力 for(int j0;jtotal_a;j){ if(dp[j]k){ // 如果获得 j 点攻击力的最小花费不超过拥有的金币数 ansmax(ans,j); // 更新最大攻击力 } } coutans\n; // 输出最多可以提升的攻击力点数 return 0; // 程序正常结束 }详细分析在完成了所有的状态转移后dp数组中存储了获得任意攻击力所需的最小金币数。最后一步只需要线性扫描一遍dp数组找出所有满足“最小花费 ≤ 玩家总金币k”的攻击力j中的最大值即为题目所求。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点逆向建模dp[j] 获得 j 攻击力的最小金币交换背包的“代价”与“价值”解决了金币数高达 109无法作为数组下标的致命问题数据范围利用total_a累加攻击力确定 DP 数组的实际遍历上界利用 n 和 a_i 较小的特点将复杂度限制在 O(n × Σa_i)01背包防重for(jtotal_a; ja[i]; j--)逆序遍历背包容量保证每件道具只被计算一次符合“每件道具只能购买一次”的题意极值初始化dp[i]INF,dp[0]0设定求最小值的基准状态确保状态转移方程min()能够正确计算出真实的最小花费答案提取if(dp[j]k) ansmax(ans,j)在预算约束下寻找最优解将计算出的“最小花费表”转化为题目要求的“最大攻击力”