P1063 [NOIP 2006 提高组] 能量项链 题解复盘模块区间动态规划目标通过调整能量珠的合并顺序使最终释放的总能量最大基本信息项目内容题目编号、来源P1063 洛谷 / NOIP 2006 提高组训练层级C 提高题知识版块区间DP、环形DP、断环成链、枚举分割点解题前 · 关键信号识别维度分析目标、约束、底层结构目标通过选择不同的相邻珠子合并顺序使释放总能量最大。约束每次只能合并相邻两颗珠子项链是一个环。底层结构一个区间最终一定是由左右两个更小区间先分别合并再进行最后一次合并因此属于区间DP由于原结构是环需要先复制数组断环成链。数据规模N≤100使用O(n³)区间DP可以通过。候选算法和依据算法环形区间DP。先把长度为 n 的环复制成长度为2n的链再计算所有长度不超过 n 的区间最优值最后枚举所有长度为 n 的区间取最大值。复杂度预判时间复杂度O(n³)空间复杂度O(n²)。解题后 · 外化复盘维度内容实现结构 / 核心思路将原数组复制一遍处理环。定义dp[l][r]表示将第l颗到第r颗珠子全部合并为一颗珠子时能够获得的最大能量。枚举区间长度、左端点和切分点k把[l,r]分成[l,k]与[k1,r]最后一次合并的贡献为v[l]*v[k1]*v[r1]。错因回溯1. 一开始容易把最后一次贡献误写成dp之间相乘实际上dp表示累计能量不是珠子标记。2. 容易不理解为什么是v[k1]和v[r1]。3. 容易只枚举原数组[1,n]忘记环需要复制后枚举2n范围。4. 最后不能直接输出dp[1][n]因为环可以从任意位置断开。边界和易错点1. 第i颗珠子的头标记是v[i]尾标记是v[i1]。2. 复制数组后v[in]v[i]。3. 区间长度最多枚举到n。4. 最终答案要枚举所有长度为n的区间。下次看到什么信号我应该想到这个方法看到“环形结构、相邻合并、不同合并顺序影响答案、最后一次操作由左右两个子区间组成”想到环形区间DP复制数组后枚举分割点。AC 完整代码#includeiostream#includequeue#includealgorithm#includevector#includeiomanipusingnamespacestd;intdp[205][205];intmain(){intn;cinn;intv[2*n2];for(inti1;in;i){cinv[i];v[in]v[i];}for(intlen2;lenn;len){for(intl1;llen-12*n;l){intrllen-1;for(intkl;kr;k){dp[l][r]max(dp[l][r],dp[l][k]dp[k1][r]v[l]*v[k1]*v[r1]);}}}intans0;for(inti1;in;i){ansmax(ans,dp[i][in-1]);}coutans;return0;}本题知识点总结1. 珠子的表示方式输入2 3 5 10实际上表示四颗珠子第1颗2 - 3 第2颗3 - 5 第3颗5 - 10 第4颗10 - 2因此第i颗珠子头 v[i] 尾 v[i1]2. 为什么要复制数组原来是一个环2 3 5 10复制后2 3 5 10 2 3 5 10这样所有可能的断环方式都对应一个长度为n的连续区间。例如[1,4] [2,5] [3,6] [4,7]分别代表从不同位置把环断开。3. 状态定义dp[l][r]表示将区间[l,r]中的所有珠子合并成一颗珠子时能够获得的最大总能量。4. 为什么枚举切分点 k区间[l................r]最后一次合并之前一定已经变成左右两颗珠子[l......k] [k1......r]因此需要枚举for(intkl;kr;k)5. 左区间最终变成什么珠子区间[l......k]最左边珠子的头永远不会改变v[l]最右边珠子的尾也不会改变。而第k颗珠子的尾是v[k1]所以左区间最终变成v[l] - v[k1]6. 右区间最终变成什么珠子区间[k1......r]最终变成v[k1] - v[r1]7. 为什么最后一次能量是v[l]*v[k1]*v[r1]最后要合并的两颗珠子分别是左珠子 v[l] - v[k1]和右珠子 v[k1] - v[r1]题目规定m - x x - n合并释放m × x × n因此v[l]*v[k1]*v[r1]8. 状态转移左右两边之前已经产生的能量dp[l][k]dp[k1][r]最后一次新产生的能量v[l]*v[k1]*v[r1]所以dp[l][r]max(dp[l][r],dp[l][k]dp[k1][r]v[l]*v[k1]*v[r1]);9. 为什么最后不能直接输出 dp[1][n]因为项链是一个环。可以从第1颗开始 第2颗开始 …… 第n颗开始任意位置断开。所以需要枚举所有长度为 n 的区间for(inti1;in;i){ansmax(ans,dp[i][in-1]);}与 P1880 石子合并对比题目状态最后一次贡献是否环形P1880 石子合并dp[l][r]sum(l,r)是P1063 能量项链dp[l][r]v[l]*v[k1]*v[r1]是两题结构完全一致复制数组 ↓ 枚举区间长度 ↓ 枚举左端点 ↓ 枚举切分点 ↓ 左右子问题 最后一次贡献 ↓ 枚举所有长度为 n 的区间取最优一句话总结看到“环形相邻合并 合并顺序影响答案”想到复制数组做环形区间DP转移的本质始终是“左区间答案 右区间答案 最后一次合并贡献”。P1064 [NOIP 2006 提高组] 金明的预算方案 题解复盘模块动态规划目标在总预算不超过 n 的情况下满足附件依赖主件的购买规则使价格×重要度总和最大基本信息项目内容题目编号、来源P1064 洛谷 / NOIP 2006 提高组训练层级C 提高题知识版块有依赖背包、分组背包、01背包、附件背包解题前 · 关键信号识别维度分析目标、约束、底层结构目标预算不超过n最大化所有已购物品的价格×重要度总和。约束附件不能单独购买必须先购买所属主件每个主件最多有两个附件。底层结构每个主件和它的附件构成一组合法购买组合再对这些组合做 01 背包。数据规模n≤32000m≤60每个主件最多两个附件可以枚举每个主件的有限种购买组合。候选算法和依据算法有依赖背包 / 分组01背包。依据单独把附件当物品做 01 背包会产生“买附件不买主件”的非法情况所以需要先把主件及附件打包成合法组合。复杂度预判每个主件最多 4 种有效组合时间复杂度约O(m×n)空间复杂度O(n)。解题后 · 外化复盘维度内容实现结构 / 核心思路先把每个附件挂到对应主件上。对于一个主件合法购买方式最多有四种只买主件、主件附件1、主件附件2、主件两个附件。随后对每个主件组做一次 01 背包容量倒序更新。错因回溯1. 容易把所有物品直接做普通 01 背包导致附件可以单独购买。2. 容量判断时容易把“价值”a1W当成“价格”a1V。3. 容量循环必须倒序否则一个主件组可能被重复使用。4. 附件需要存到它所属主件的编号q下而不是按附件自己的编号处理。边界和易错点1.q0表示主件。2. 附件最多两个因此只需要保存附件1和附件2。3. 价值为价格×重要度。4. 没有主件的编号要跳过。5. 每组只能选择一种合法组合因此仍然属于 01 背包思想。下次看到什么信号我应该想到这个方法看到“附件依赖主件”“必须先选某个物品才能选另一个物品”“每个主件带少量附件”想到有依赖背包把主件及附件整理成合法组合后做 01 背包。AC 完整代码#includeiostream#includequeue#includealgorithm#includevector#includeiomanipusingnamespacestd;constintN65;constintM32005;intmainV[N],mainW[N];inta1V[N],a1W[N];inta2V[N],a2W[N];intdp[M];intmain(){intn,m;cinnm;for(inti1;im;i){intv,w,q;cinvwq;if(q0){mainV[i]v;mainW[i]v*w;}else{if(a1V[q]0){a1V[q]v;a1W[q]v*w;}else{a2V[q]v;a2W[q]v*w;}}}for(inti1;im;i){if(mainV[i]0)continue;for(intjn;jmainV[i];j--){dp[j]max(dp[j],dp[j-mainV[i]]mainW[i]);if(a1V[i]ja1V[i]mainV[i]){dp[j]max(dp[j],dp[j-mainV[i]-a1V[i]]mainW[i]a1W[i]);}if(a2V[i]jmainV[i]a2V[i]){dp[j]max(dp[j],dp[j-mainV[i]-a2V[i]]mainW[i]a2W[i]);}if(a1V[i]a2V[i]jmainV[i]a1V[i]a2V[i]){dp[j]max(dp[j],dp[j-mainV[i]-a1V[i]-a2V[i]]mainW[i]a1W[i]a2W[i]);}}}coutdp[n];return0;}本题知识点总结1. 为什么不能直接做普通 01 背包假设主件电脑 附件打印机题目规定买打印机 必须买电脑如果把它们直接当两个独立物品做 01 背包就可能出现只买打印机这是非法方案。所以必须把主件 附件作为一个整体考虑。2. 一个主件有哪些合法组合假设主件 M 附件 A 附件 B合法情况只有M MA MB MAB不合法A B AB因为附件不能脱离主件。3. 为什么这是“分组背包”思想对于每一个主件组主件 ├── 附件1 └── 附件2我们可以从这一组中选择不买 或者 四种合法方案中的一种不同主件组之间相互独立。所以本质是每个主件及其附件构成一组在组内枚举合法组合再做 01 背包。4. 状态定义dp[j]表示预算不超过j元时能够获得的最大价值。其中价值价值价格 × 重要度5. 只买主件价格mainV[i]价值mainW[i]所以dp[j]max(dp[j],dp[j-mainV[i]]mainW[i]);6. 主件 附件1总价格mainV[i]a1V[i]总价值mainW[i]a1W[i]转移dp[j]max(dp[j],dp[j-mainV[i]-a1V[i]]mainW[i]a1W[i]);7. 主件 附件2同理dp[j]max(dp[j],dp[j-mainV[i]-a2V[i]]mainW[i]a2W[i]);8. 主件 两个附件总价格mainV[i]a1V[i]a2V[i]总价值mainW[i]a1W[i]a2W[i]所以dp[j]max(dp[j],dp[j-mainV[i]-a1V[i]-a2V[i]]mainW[i]a1W[i]a2W[i]);9. 为什么容量倒序因为每个主件组只能使用一次。如果正序枚举for(intjmainV[i];jn;j)本轮刚刚更新出的状态可能继续被当前主件组使用相当于同一个主件买了两次所以必须for(intjn;jmainV[i];j--)与普通01背包对比模型每组可选情况普通01背包不选 / 选当前物品金明的预算方案不选 / 主件 / 主件附件1 / 主件附件2 / 主件两个附件本质仍然是从当前组的合法方案中选一种再进行 01 背包转移。一句话总结看到“附件必须依赖主件”不要把附件单独做背包先把每个主件和附件组成合法购买组合再按主件组做 01 背包。