打卡信奥刷题系列第2809篇今天选的题目是P4138 [JOISC 2014] 挂饰 / Straps。这道题拿到第一眼容易误判成模拟挂着挂着不就行了但它其实是一个很经典的背包问题变种考察的是对“可变容量背包”的理解。JOISC的题通常不会让你一眼看出做法这道题也不例外。它适合正在刷动态规划、背包专题的选手特别是那些已经会普通01背包但遇到“背包容量会随选择变化”就开始头疼的同学。我会从题目分析、状态设计、C代码实现到常见坑点完整过一遍最后再聊聊这类题在比赛里怎么举一反三。1. 先看懂题目挂饰问题的本质是“库存管理”1.1 还原原题场景题面大意是这样的你有一条带子上面可以挂装饰品。一开始带子上有1个挂钩接下来有n个挂饰每个挂饰有两个属性a_i表示这个挂饰上自带多少个挂钩b_i表示挂上它能获得的美观价值。注意b_i可以是负数也就是说有的挂饰挂上去反而会扣分。每次挂一个挂饰需要占用当前带子上的一个空闲挂钩挂完之后这个挂饰自带的a_i个挂钩就成为新的可用挂钩可供后续使用。也就是说每挂一个挂饰带子上的挂钩数量变化是a_i - 1。目标是从这n个挂饰中选一些挂上去让总价值最大你可以不挂任何一个。中途如果挂钩数变成0就不能再继续挂了但当前已经选好的方案仍然有效。数据范围一般是n ≤ 2000这就暗示做法大概率是O(n^2)级别的动态规划。如果n到2e5那肯定另有巧妙排序或贪心但2000这个数据范围就是明摆着让你想二维状态的。1.2 把故事翻译成数学模型如果你刷过背包你会发现这题本质上是一个“容量会变的背包”。普通01背包里背包容量固定是V每件物品有重量w_i和价值v_i选或不选最后看容量范围内价值最大是多少。但这里不一样如果当前挂钩数是j选了一个挂饰后挂钩数会变成j j - 1 a_i这个j可能比j大也可能比j小取决于a_i。如果a_i ≥ 1挂钩数不会减少如果a_i 0挂钩数就减少1。约束条件是什么要能挂这个挂饰必须有挂钩也就是当前j必须大于0。挂完之后如果j变成0那没关系只不过接下来不能再挂了。所以整个模型可以抽象成状态当前剩余挂钩数。决策选或不选某个挂饰。约束转移前j 0。目标最大化选中的b_i之和。这个模型的好处是它把“顺序”问题变成了“状态”问题。你不需要去关心挂饰是先挂哪个后挂哪个只要最终效果是某个挂钩数对应的价值顺序就被压缩进状态里了。1.3 为什么不能直接排序贪心不少新手看到这题第一反应是把价值b_i从大到小排序一个个挂上去不就完了但很快就会发现不行。举一个最简单的反例。两个挂饰挂饰Aa0, b100挂饰Ba1, b-1初始挂钩数是1。如果先挂A挂钩数变0B挂不上总价值是100。如果先挂B挂钩数变1再挂A挂钩数变0总价值是99。所以最优解是只挂A。这里的顺序直接影响了可行性但价值排序根本看不出来。再举一个更有意思的反例来说明“负价值”也不一定就该扔掉挂饰Ca2, b-5挂饰Da0, b10初始挂钩数1。如果只挂D价值10挂完挂钩变0。如果先挂C挂钩数变2再挂D挂钩数变1总价值是5。虽然C价值是-5但因为它提供了额外挂钩反而让D有机会被挂上最终结果比只挂D好不对这里5 10所以只挂D更好。我把例子改一下挂饰Ca2, b-5挂饰Ea0, b20只挂E是20先挂C再挂E是15还是不如只挂E。看来要构造一个负价值必须选的情况需要多个高价值且a0的挂饰挂饰Ca2, b-5挂饰Ea0, b20挂饰Fa0, b20初始挂钩1。如果直接挂E和F挂E后挂钩变0F挂不上只能得到20。如果先挂C挂钩变2然后挂E和F最后挂钩变0总价值35。所以C虽然价值是负的但它提供了额外一个挂钩的“容量”让另外两个高价值挂饰都有机会挂上。看到这里你应该明白这个问题不是简单排序能解决的必须把“当前挂钩数”当成资源来管理。而资源会变化正是动态规划的用武之地。2. 设计DP挂钩数量就是状态量2.1 状态定义既然挂钩数是最关键的资源最自然的状态就是处理完若干个挂饰后当前剩余挂钩数为j时能获得的最大价值。设dp[j]表示在当前已经决策完前i个挂饰的情况下剩余挂钩数为j时的最大总价值。初始时挂钩数是1价值是0所以dp[1] 0。其他dp[j]都设为负无穷表示这些状态不可达。这里有个容易忽略的细节dp[0]初始不能是0。因为一开始挂钩数不可能是0挂钩数是0意味着你一开始就没有能力挂任何东西这个状态不应存在。但转移过程中dp[0]可以作为某个方案的结果存在比如把最后一个挂饰挂上去挂钩数恰好变成0那这个方案是合法的。为什么用“当前剩余挂钩数”而不是“已经用了多少个挂钩”因为未来的决策只依赖于剩余多少挂钩这和普通背包的“剩余容量”思路完全一致。你不需要知道挂饰的具体顺序只需要知道当前可用资源量。2.2 转移方程对于第i个挂饰设它的挂钩数为a价值为b有两种决策不选状态原封不动dp[j]保留。选前提是当前j 0。如果选了新的挂钩数变成 j j - 1 a价值增加b即ndp[j] max(ndp[j], dp[j] b)这句话翻译成代码就是每处理一个挂饰先拷贝一份旧dp作为“不选”的结果然后遍历所有j只要dp[j]可达就尝试去更新ndp[j]。循环结束后用ndp替换dp继续处理下一个挂饰。这个转移的复杂度是O(n^2)因为每件物品要遍历j从1到n。n ≤ 2000时总操作约400万次C完全没问题。2.3 为什么不能直接用简单的一维滚动如果你背过01背包的一维滚动写法可能会想我能不能用一个dp数组内层循环倒着跑直接原地更新答案是千万不要这个题的容量是可增可减的简单倒序会出大问题。举个反例。一件物品a0b5当前dp[1]0dp[2]10dp[3]20。如果按普通01背包的习惯倒序遍历jj3时new_j2dp[2]更新为max(10, 205)25j2时new_j1dp[1]更新为max(0, 255)30看起来好像没事但你注意到没有这里用到的dp[2]已经是刚被更新过的25它其实代表了“已经从j3状态选过一次这件物品”。继续用25去更新dp[1]相当于同一件物品选了两次这显然不对。为什么普通01背包倒序就没有这个问题因为普通背包里容量只会变小j-w一定小于j倒序遍历时j-w还没有被本轮更新读取的是旧值。但本题a0时容量也变小为什么还会错关键在于普通背包是“从大容量推导小容量”用的是dp[j-w]来更新dp[j]而这里是“从小容量推导大容量或小容量”方向不统一。最稳妥的写法就是每轮用一个新的数组ndp先拷贝dp然后只基于旧dp去更新ndp。这样无论容量变大还是变小都不会污染本轮的状态。这就是我下面代码里采用的方式也是我最推荐你写的方式。3. C完整实现与运行细节3.1 核心代码思路整体流程分成四步读入n和每个挂饰的a、b。初始化dp数组dp[1] 0其余为负无穷。逐个处理挂饰拷贝ndp遍历所有可达j尝试转移。最终答案取dp[0]到dp[n]的最大值因为最终挂钩数多少不重要价值最大才行。注意转移的时候new_j j - 1 a这个值可能超过n。因为最多只有n个挂饰挂钩数超过n时多余部分在后续选择中根本用不完所以可以直接截断到n。这个操作不会丢解后面我会专门解释。3.2 关于挂钩数上限的微调你可能想问为什么上限是n不是更大的数假设第一个挂饰a2000n也是2000挂完之后挂钩数变成2000超过n了。但是你能利用的挂钩数再多后续最多也就再挂n-1个挂饰其中每个挂饰最多消耗1个挂钩。所以挂钩数只要达到n就已经是“绝对够用”的状态再多没有实际意义。所以每次算完new_j后如果new_j n就把它设置成n。这样数组大小固定为n1实现简单也不会漏解。再验证一下截断的正确性。假设n2第一个挂饰a100b10第二个挂饰a0b5。初始dp[1]0。处理第一个挂饰后真实挂钩数是100截断存到dp[2]10。处理第二个挂饰时从dp[2]转移new_j2-101dp[1]15。就算不截断从挂钩数100转移到99最后也是选完这个挂饰价值15。所以截断不影响结果。3.3 完整代码清单直接上C17代码注释写得比较详细方便你直接抄去提交。#include bits/stdc.h using namespace std; const long long INF (1LL 60); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1), b(n 1); for (int i 1; i n; i) { cin a[i] b[i]; } // dp[j] 表示当前剩余挂钩数为 j 时的最大价值 vectorlong long dp(n 1, -INF); dp[1] 0; // 初始带子上有 1 个挂钩 for (int i 1; i n; i) { // 不选第 i 个挂饰的情况 vectorlong long ndp dp; for (int j 1; j n; j) { if (dp[j] -INF) continue; // 这个状态不可达 int nj j - 1 a[i]; if (nj n) nj n; // 挂钩数足够多截断到 n // 选第 i 个挂饰价值加上 b[i] ndp[nj] max(ndp[nj], dp[j] b[i]); } dp.swap(ndp); } long long ans 0; // 至少可以什么都不挂价值为 0 for (int j 0; j n; j) { ans max(ans, dp[j]); } cout ans \n; return 0; }这段代码的复杂度是O(n^2)空间是O(n)参考用时在n2000时非常快提交基本是秒过。3.4 复杂度与运行表现时间复杂度外层n次内层j从1到n总共O(n^2)。加上每次拷贝ndp的O(n)总体还是O(n^2)。空间复杂度两个长度n1的vectorO(n)。如果你担心拷贝开销其实这个拷贝就是O(n)对总复杂度没有任何影响。实际跑起来n2000时约400万次转移加2000次数组拷贝几乎感觉不到时间。4. 常见错误、坑点与调试方法4.1 初始化和INF选择不当最常见的一个错误把dp数组整体初始化为0。如果dp[0]初始为0那从挂钩数0的状态出发就可以继续“挂”东西了相当于一开始就凭空获得了资源答案会被放大。比如样例中可能出现只有一件物品a0, b10的情况初始挂钩1。如果dp[0]0处理该物品时从j1转移到nj0ndp[0]max(0, 10)10这还正常。但如果dp[0]0被当成可达状态后续就可能从0挂钩继续转移搞出非法结果。所以dp[1]0其他全部负无穷绝不手软。INF建议用1e18这种足够大的数同时更新前判断dp[j]是否等于-INF。判断的时候用dp[j] -INF是可以的因为你所有不可达状态都是同一个-INF转移时也只从可达状态改写不会产生一个又等于-INF又没问题的新值。不过更保险的写法是if (dp[j] -INF / 2) continue;防止有极端负价值累加出比-INF稍微大一点的值。两种写法本人都试过推荐后者写起来也顺手。4.2 上限截断的边界没处理好new_j j - 1 a[i]注意j的最小值是1所以new_j最小是0。只要a[i] 0new_j就不会小于0。题目里挂饰自带的挂钩数不可能是负数所以这点可以放心。但new_j可能非常大如果你不做截断vector下标访问越界本地可能不报错提交就各种奇怪结果。务必在更新前检查或者像代码里那样直接截断到n。另外最终答案的循环一定要从j0开始不是从1开始。因为可能最优方案刚好把所有挂钩用完最后挂钩数为0比如挂了一堆a0的挂饰。漏掉dp[0]会让你在部分数据上少拿分数。4.3 负价值挂饰的处理思路负价值的挂饰要不要选很多选手看到b为负第一反应就是跳过。但如果你过早地做这个“剪枝”就会漏掉上面那种“负价值换容量”的情况。举个例子有两件物品物品Xa100, b-1000物品Ya0, b5000。初始挂钩1。如果你把负价值的X扔了那只能挂Y得5000。但先挂X挂钩数变100再挂Y挂钩数变99总价值4000确实不如只挂Y。可如果Y有10个呢你可以先挂X再挂10个Y最后总价值是40000-100039000远超只挂一个Y的5000。所以负价值挂饰有时是“必要的投资”。DP处理负价值完全没问题因为它会把所有可能都算进去。真正需要你想清楚的是不要自己加“b必须大于0”这种限制条件交给状态转移自然决定。4.4 调试建议个人调试这类DP题最有效的三个手段第一写一个暴力枚举的验证程序。n小的时候直接枚举所有子集检查每种选法是否合法暴力算最大值再跟DP结果对拍。这个对拍能帮你快速抓出状态定义的问题。第二把每轮dp数组打出来。n3按时你可以在循环里输出当前dp值看看哪些状态被更新了哪一步出现了不该出现的转移。尤其注意dp[0]是不是被不当使用。第三造一些极端数据。比如所有a都是0初始挂钩1那最多挂一个挂饰答案就是所有正价值b的最大值。再比如某个a特别大大到超过n验证截断逻辑。这些边界数据往往能暴露隐藏的数组越界。5. 举一反三从“挂饰”看一类动态背包问题5.1 题型识别容量可以改变的背包刷题多了你会发现很多看似毫无关联的题抽象出来都是“当前资源量作为状态选择会改变资源量”的模型。一类典型特征是每件物品占用单位资源但会提供额外资源。比如游戏里你有一个“行动力”系统做任务消耗行动力但完成后会奖励行动力同时获得积分又比如你有初始预算投资一个项目消耗资金项目成功后又能产生更多资金同时获得收益。这类问题如果数据范围不大都可以用类似本题的DP解法。关键思路是把资源量j直接作为状态的一维不要试图去排序或者贪心因为资源的增减会打破局部的优劣顺序。只要转移满足“从旧状态推新状态”的条件就可以用动态规划。5.2 几道容易联想的变式如果你熟悉竞赛题会发现这个模型还能往几个方向扩展。第一个方向是物品顺序受限。比如某些挂饰必须出现在另一些挂饰之前这时你需要额外记录哪些已经选了复杂度会上来往往n会变小。第二个方向是资源上限严格。比如要求最终挂钩数至少为k那答案是dp数组中j≥k的最大值或者转移时只保留j≥k的状态。第三个方向是价值也可能影响资源比如某些挂饰的价值本身也是挂钩数的一部分这时状态需要扩展成二维dp[i][j]表示前i个物品且当前资源为j的最大收益做法还是类似的。这些变式在比赛里经常出现核心都是“不要害怕状态定义里出现资源量”它往往就是最朴素、最可靠的状态。5.3 比赛中的实战建议十几分钟限时内怎么快速解出这类题我的习惯是拿到题先重述题意把“资源变化”这个关键词圈出来。一旦发现“选择一个物品后某个数量会变化而且变化量由物品决定”就立刻警觉这八成是背包变种。然后决定状态dp[j]表示当前资源量为j的最优答案。初始资源量是多少就把dp[初始值]设成0。转移时注意资源量上限要么是题目给的要么是n超过就截断。最后写代码时坚持“新数组转移”而不是手动滚动。虽然滚动数组看起来高级但在这类容量可变的题里很容易写错。先提交一份正确但略微朴素的代码等后面时间充裕再考虑优化。我个人在实际操作中的体会是这类“资源可变背包”比普通背包更容易在细节上翻车但结构上反而更简单——因为状态里已经包含了资源量不需要额外思考顺序。如果你能把这道P4138彻底吃透再去碰类似的题目基本都能一眼看穿模型。最后再分享一个小技巧遇到不确定的状态转移别急着写代码先拿一支笔把自己假设的dp数组画出来模拟跑一遍样例。动态规划是“把可能性算清楚”而不是“把方案背下来”。这道挂饰题就是个很好的锻炼刷完它你会对“可变背包”这个模型建立非常牢靠的手感。 
长河君 · 2026/10/16 13:31:09 · 阅读 1.2k 信奥P4138挂饰题解：可变容量背包的动态规划技巧
打卡信奥刷题系列第2809篇今天选的题目是P4138 [JOISC 2014] 挂饰 / Straps。这道题拿到第一眼容易误判成模拟挂着挂着不就行了但它其实是一个很经典的背包问题变种考察的是对“可变容量背包”的理解。JOISC的题通常不会让你一眼看出做法这道题也不例外。它适合正在刷动态规划、背包专题的选手特别是那些已经会普通01背包但遇到“背包容量会随选择变化”就开始头疼的同学。我会从题目分析、状态设计、C代码实现到常见坑点完整过一遍最后再聊聊这类题在比赛里怎么举一反三。1. 先看懂题目挂饰问题的本质是“库存管理”1.1 还原原题场景题面大意是这样的你有一条带子上面可以挂装饰品。一开始带子上有1个挂钩接下来有n个挂饰每个挂饰有两个属性a_i表示这个挂饰上自带多少个挂钩b_i表示挂上它能获得的美观价值。注意b_i可以是负数也就是说有的挂饰挂上去反而会扣分。每次挂一个挂饰需要占用当前带子上的一个空闲挂钩挂完之后这个挂饰自带的a_i个挂钩就成为新的可用挂钩可供后续使用。也就是说每挂一个挂饰带子上的挂钩数量变化是a_i - 1。目标是从这n个挂饰中选一些挂上去让总价值最大你可以不挂任何一个。中途如果挂钩数变成0就不能再继续挂了但当前已经选好的方案仍然有效。数据范围一般是n ≤ 2000这就暗示做法大概率是O(n^2)级别的动态规划。如果n到2e5那肯定另有巧妙排序或贪心但2000这个数据范围就是明摆着让你想二维状态的。1.2 把故事翻译成数学模型如果你刷过背包你会发现这题本质上是一个“容量会变的背包”。普通01背包里背包容量固定是V每件物品有重量w_i和价值v_i选或不选最后看容量范围内价值最大是多少。但这里不一样如果当前挂钩数是j选了一个挂饰后挂钩数会变成j j - 1 a_i这个j可能比j大也可能比j小取决于a_i。如果a_i ≥ 1挂钩数不会减少如果a_i 0挂钩数就减少1。约束条件是什么要能挂这个挂饰必须有挂钩也就是当前j必须大于0。挂完之后如果j变成0那没关系只不过接下来不能再挂了。所以整个模型可以抽象成状态当前剩余挂钩数。决策选或不选某个挂饰。约束转移前j 0。目标最大化选中的b_i之和。这个模型的好处是它把“顺序”问题变成了“状态”问题。你不需要去关心挂饰是先挂哪个后挂哪个只要最终效果是某个挂钩数对应的价值顺序就被压缩进状态里了。1.3 为什么不能直接排序贪心不少新手看到这题第一反应是把价值b_i从大到小排序一个个挂上去不就完了但很快就会发现不行。举一个最简单的反例。两个挂饰挂饰Aa0, b100挂饰Ba1, b-1初始挂钩数是1。如果先挂A挂钩数变0B挂不上总价值是100。如果先挂B挂钩数变1再挂A挂钩数变0总价值是99。所以最优解是只挂A。这里的顺序直接影响了可行性但价值排序根本看不出来。再举一个更有意思的反例来说明“负价值”也不一定就该扔掉挂饰Ca2, b-5挂饰Da0, b10初始挂钩数1。如果只挂D价值10挂完挂钩变0。如果先挂C挂钩数变2再挂D挂钩数变1总价值是5。虽然C价值是-5但因为它提供了额外挂钩反而让D有机会被挂上最终结果比只挂D好不对这里5 10所以只挂D更好。我把例子改一下挂饰Ca2, b-5挂饰Ea0, b20只挂E是20先挂C再挂E是15还是不如只挂E。看来要构造一个负价值必须选的情况需要多个高价值且a0的挂饰挂饰Ca2, b-5挂饰Ea0, b20挂饰Fa0, b20初始挂钩1。如果直接挂E和F挂E后挂钩变0F挂不上只能得到20。如果先挂C挂钩变2然后挂E和F最后挂钩变0总价值35。所以C虽然价值是负的但它提供了额外一个挂钩的“容量”让另外两个高价值挂饰都有机会挂上。看到这里你应该明白这个问题不是简单排序能解决的必须把“当前挂钩数”当成资源来管理。而资源会变化正是动态规划的用武之地。2. 设计DP挂钩数量就是状态量2.1 状态定义既然挂钩数是最关键的资源最自然的状态就是处理完若干个挂饰后当前剩余挂钩数为j时能获得的最大价值。设dp[j]表示在当前已经决策完前i个挂饰的情况下剩余挂钩数为j时的最大总价值。初始时挂钩数是1价值是0所以dp[1] 0。其他dp[j]都设为负无穷表示这些状态不可达。这里有个容易忽略的细节dp[0]初始不能是0。因为一开始挂钩数不可能是0挂钩数是0意味着你一开始就没有能力挂任何东西这个状态不应存在。但转移过程中dp[0]可以作为某个方案的结果存在比如把最后一个挂饰挂上去挂钩数恰好变成0那这个方案是合法的。为什么用“当前剩余挂钩数”而不是“已经用了多少个挂钩”因为未来的决策只依赖于剩余多少挂钩这和普通背包的“剩余容量”思路完全一致。你不需要知道挂饰的具体顺序只需要知道当前可用资源量。2.2 转移方程对于第i个挂饰设它的挂钩数为a价值为b有两种决策不选状态原封不动dp[j]保留。选前提是当前j 0。如果选了新的挂钩数变成 j j - 1 a价值增加b即ndp[j] max(ndp[j], dp[j] b)这句话翻译成代码就是每处理一个挂饰先拷贝一份旧dp作为“不选”的结果然后遍历所有j只要dp[j]可达就尝试去更新ndp[j]。循环结束后用ndp替换dp继续处理下一个挂饰。这个转移的复杂度是O(n^2)因为每件物品要遍历j从1到n。n ≤ 2000时总操作约400万次C完全没问题。2.3 为什么不能直接用简单的一维滚动如果你背过01背包的一维滚动写法可能会想我能不能用一个dp数组内层循环倒着跑直接原地更新答案是千万不要这个题的容量是可增可减的简单倒序会出大问题。举个反例。一件物品a0b5当前dp[1]0dp[2]10dp[3]20。如果按普通01背包的习惯倒序遍历jj3时new_j2dp[2]更新为max(10, 205)25j2时new_j1dp[1]更新为max(0, 255)30看起来好像没事但你注意到没有这里用到的dp[2]已经是刚被更新过的25它其实代表了“已经从j3状态选过一次这件物品”。继续用25去更新dp[1]相当于同一件物品选了两次这显然不对。为什么普通01背包倒序就没有这个问题因为普通背包里容量只会变小j-w一定小于j倒序遍历时j-w还没有被本轮更新读取的是旧值。但本题a0时容量也变小为什么还会错关键在于普通背包是“从大容量推导小容量”用的是dp[j-w]来更新dp[j]而这里是“从小容量推导大容量或小容量”方向不统一。最稳妥的写法就是每轮用一个新的数组ndp先拷贝dp然后只基于旧dp去更新ndp。这样无论容量变大还是变小都不会污染本轮的状态。这就是我下面代码里采用的方式也是我最推荐你写的方式。3. C完整实现与运行细节3.1 核心代码思路整体流程分成四步读入n和每个挂饰的a、b。初始化dp数组dp[1] 0其余为负无穷。逐个处理挂饰拷贝ndp遍历所有可达j尝试转移。最终答案取dp[0]到dp[n]的最大值因为最终挂钩数多少不重要价值最大才行。注意转移的时候new_j j - 1 a这个值可能超过n。因为最多只有n个挂饰挂钩数超过n时多余部分在后续选择中根本用不完所以可以直接截断到n。这个操作不会丢解后面我会专门解释。3.2 关于挂钩数上限的微调你可能想问为什么上限是n不是更大的数假设第一个挂饰a2000n也是2000挂完之后挂钩数变成2000超过n了。但是你能利用的挂钩数再多后续最多也就再挂n-1个挂饰其中每个挂饰最多消耗1个挂钩。所以挂钩数只要达到n就已经是“绝对够用”的状态再多没有实际意义。所以每次算完new_j后如果new_j n就把它设置成n。这样数组大小固定为n1实现简单也不会漏解。再验证一下截断的正确性。假设n2第一个挂饰a100b10第二个挂饰a0b5。初始dp[1]0。处理第一个挂饰后真实挂钩数是100截断存到dp[2]10。处理第二个挂饰时从dp[2]转移new_j2-101dp[1]15。就算不截断从挂钩数100转移到99最后也是选完这个挂饰价值15。所以截断不影响结果。3.3 完整代码清单直接上C17代码注释写得比较详细方便你直接抄去提交。#include bits/stdc.h using namespace std; const long long INF (1LL 60); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1), b(n 1); for (int i 1; i n; i) { cin a[i] b[i]; } // dp[j] 表示当前剩余挂钩数为 j 时的最大价值 vectorlong long dp(n 1, -INF); dp[1] 0; // 初始带子上有 1 个挂钩 for (int i 1; i n; i) { // 不选第 i 个挂饰的情况 vectorlong long ndp dp; for (int j 1; j n; j) { if (dp[j] -INF) continue; // 这个状态不可达 int nj j - 1 a[i]; if (nj n) nj n; // 挂钩数足够多截断到 n // 选第 i 个挂饰价值加上 b[i] ndp[nj] max(ndp[nj], dp[j] b[i]); } dp.swap(ndp); } long long ans 0; // 至少可以什么都不挂价值为 0 for (int j 0; j n; j) { ans max(ans, dp[j]); } cout ans \n; return 0; }这段代码的复杂度是O(n^2)空间是O(n)参考用时在n2000时非常快提交基本是秒过。3.4 复杂度与运行表现时间复杂度外层n次内层j从1到n总共O(n^2)。加上每次拷贝ndp的O(n)总体还是O(n^2)。空间复杂度两个长度n1的vectorO(n)。如果你担心拷贝开销其实这个拷贝就是O(n)对总复杂度没有任何影响。实际跑起来n2000时约400万次转移加2000次数组拷贝几乎感觉不到时间。4. 常见错误、坑点与调试方法4.1 初始化和INF选择不当最常见的一个错误把dp数组整体初始化为0。如果dp[0]初始为0那从挂钩数0的状态出发就可以继续“挂”东西了相当于一开始就凭空获得了资源答案会被放大。比如样例中可能出现只有一件物品a0, b10的情况初始挂钩1。如果dp[0]0处理该物品时从j1转移到nj0ndp[0]max(0, 10)10这还正常。但如果dp[0]0被当成可达状态后续就可能从0挂钩继续转移搞出非法结果。所以dp[1]0其他全部负无穷绝不手软。INF建议用1e18这种足够大的数同时更新前判断dp[j]是否等于-INF。判断的时候用dp[j] -INF是可以的因为你所有不可达状态都是同一个-INF转移时也只从可达状态改写不会产生一个又等于-INF又没问题的新值。不过更保险的写法是if (dp[j] -INF / 2) continue;防止有极端负价值累加出比-INF稍微大一点的值。两种写法本人都试过推荐后者写起来也顺手。4.2 上限截断的边界没处理好new_j j - 1 a[i]注意j的最小值是1所以new_j最小是0。只要a[i] 0new_j就不会小于0。题目里挂饰自带的挂钩数不可能是负数所以这点可以放心。但new_j可能非常大如果你不做截断vector下标访问越界本地可能不报错提交就各种奇怪结果。务必在更新前检查或者像代码里那样直接截断到n。另外最终答案的循环一定要从j0开始不是从1开始。因为可能最优方案刚好把所有挂钩用完最后挂钩数为0比如挂了一堆a0的挂饰。漏掉dp[0]会让你在部分数据上少拿分数。4.3 负价值挂饰的处理思路负价值的挂饰要不要选很多选手看到b为负第一反应就是跳过。但如果你过早地做这个“剪枝”就会漏掉上面那种“负价值换容量”的情况。举个例子有两件物品物品Xa100, b-1000物品Ya0, b5000。初始挂钩1。如果你把负价值的X扔了那只能挂Y得5000。但先挂X挂钩数变100再挂Y挂钩数变99总价值4000确实不如只挂Y。可如果Y有10个呢你可以先挂X再挂10个Y最后总价值是40000-100039000远超只挂一个Y的5000。所以负价值挂饰有时是“必要的投资”。DP处理负价值完全没问题因为它会把所有可能都算进去。真正需要你想清楚的是不要自己加“b必须大于0”这种限制条件交给状态转移自然决定。4.4 调试建议个人调试这类DP题最有效的三个手段第一写一个暴力枚举的验证程序。n小的时候直接枚举所有子集检查每种选法是否合法暴力算最大值再跟DP结果对拍。这个对拍能帮你快速抓出状态定义的问题。第二把每轮dp数组打出来。n3按时你可以在循环里输出当前dp值看看哪些状态被更新了哪一步出现了不该出现的转移。尤其注意dp[0]是不是被不当使用。第三造一些极端数据。比如所有a都是0初始挂钩1那最多挂一个挂饰答案就是所有正价值b的最大值。再比如某个a特别大大到超过n验证截断逻辑。这些边界数据往往能暴露隐藏的数组越界。5. 举一反三从“挂饰”看一类动态背包问题5.1 题型识别容量可以改变的背包刷题多了你会发现很多看似毫无关联的题抽象出来都是“当前资源量作为状态选择会改变资源量”的模型。一类典型特征是每件物品占用单位资源但会提供额外资源。比如游戏里你有一个“行动力”系统做任务消耗行动力但完成后会奖励行动力同时获得积分又比如你有初始预算投资一个项目消耗资金项目成功后又能产生更多资金同时获得收益。这类问题如果数据范围不大都可以用类似本题的DP解法。关键思路是把资源量j直接作为状态的一维不要试图去排序或者贪心因为资源的增减会打破局部的优劣顺序。只要转移满足“从旧状态推新状态”的条件就可以用动态规划。5.2 几道容易联想的变式如果你熟悉竞赛题会发现这个模型还能往几个方向扩展。第一个方向是物品顺序受限。比如某些挂饰必须出现在另一些挂饰之前这时你需要额外记录哪些已经选了复杂度会上来往往n会变小。第二个方向是资源上限严格。比如要求最终挂钩数至少为k那答案是dp数组中j≥k的最大值或者转移时只保留j≥k的状态。第三个方向是价值也可能影响资源比如某些挂饰的价值本身也是挂钩数的一部分这时状态需要扩展成二维dp[i][j]表示前i个物品且当前资源为j的最大收益做法还是类似的。这些变式在比赛里经常出现核心都是“不要害怕状态定义里出现资源量”它往往就是最朴素、最可靠的状态。5.3 比赛中的实战建议十几分钟限时内怎么快速解出这类题我的习惯是拿到题先重述题意把“资源变化”这个关键词圈出来。一旦发现“选择一个物品后某个数量会变化而且变化量由物品决定”就立刻警觉这八成是背包变种。然后决定状态dp[j]表示当前资源量为j的最优答案。初始资源量是多少就把dp[初始值]设成0。转移时注意资源量上限要么是题目给的要么是n超过就截断。最后写代码时坚持“新数组转移”而不是手动滚动。虽然滚动数组看起来高级但在这类容量可变的题里很容易写错。先提交一份正确但略微朴素的代码等后面时间充裕再考虑优化。我个人在实际操作中的体会是这类“资源可变背包”比普通背包更容易在细节上翻车但结构上反而更简单——因为状态里已经包含了资源量不需要额外思考顺序。如果你能把这道P4138彻底吃透再去碰类似的题目基本都能一眼看穿模型。最后再分享一个小技巧遇到不确定的状态转移别急着写代码先拿一支笔把自己假设的dp数组画出来模拟跑一遍样例。动态规划是“把可能性算清楚”而不是“把方案背下来”。这道挂饰题就是个很好的锻炼刷完它你会对“可变背包”这个模型建立非常牢靠的手感。