我第一次见到“能量项链”这道题是在一份区间DP经典题目清单里。题目名字很文艺实际规则却极其“公式化”N颗珠子围成一个环每颗珠子有头、尾两个标记相邻两颗珠子合并会释放能量合并后的新珠子又带着新的头尾标记继续参与合并最后要找到一种合并顺序让总能量最大。当年我一度以为它只是“环形石子合并”的换皮题套了石子合并的状态转移上去样例直接不对劲。后来才反应过来这道题其实是一道标准的区间DP而且内核和“矩阵链乘”几乎同构只是外面包了一层项链的外壳。这篇文章适合准备竞赛的选手、正在学动态规划的初学者以及带学生刷DP题的教练。我会把题目识别、状态设计、转移推导、环形展开、代码实现和常见坑全部展开讲还会讲一些我在实际做题和辅导别人时踩过的细节。如果你能把这道题彻底吃透区间DP这一类题基本就通了一半。1. 为什么说“能量项链”是一道容易被误判的区间DP1.1 先把题目规则彻底还原一遍题目描述是这样的有N颗珠子串成一个环第i颗珠子有两个标记分别叫头标记和尾标记。相邻的两颗珠子假设是珠子A和珠子B如果A的尾标记等于B的头标记那么它们可以合并成一颗新珠子。新珠子会继承A的头标记和B的尾标记合并过程中产生的能量是A的头标记 × A的尾标记 × B的尾标记因为首尾相接的环是闭合的所以不存在绝对的“第一颗”和“最后一颗”这也是最容易理解错的地方之一。题目要求选择一种合并顺序把N颗珠子合并成一整颗使得释放的总能量最大。这里有一个非常关键的数学细节题目会把所有珠子的头标记按顺序给出来比如N4时给的是a[1]、a[2]、a[3]、a[4]那么第i颗珠子的头标记是a[i]尾标记则是a[i1]第4颗珠子的尾标记就是a[1]相当于整个标记序列在环上循环。所以本质上我们手里不是N个孤立数字而是N个相邻的数字对。这个“数字对”才是珠子不是单个数字。1.2 它和“石子合并”长得像但权值机制完全不同很多人第一眼会把这道题归到“合并相邻元素求最大代价”的模板里然后套石子合并的写法dp[l][r] max(dp[l][k] dp[k1][r] sum(l, r))这个转移在石子合并里是正确的因为合并代价是两堆石子的重量总和。但能量项链的合并代价不是区间和而是三个端点标记相乘。它不关心区间里到底有多少“总和”只关心合并时左右两端的标记和衔接处的标记。这是我见过最多人踩的坑。如果你只记住“区间DP就是枚举分割点”这句话却忽略了代价函数的具体形态就会写出一个看起来很像、实际上完全错误的转移方程。必须提醒的是区间DP的关键从来不是“要不要枚举分割点”而是“合并代价到底由什么决定”。1.3 这类题的共同特征合并过程对应一棵二叉树想识别一道题是不是区间DP可以看三个信号操作必须是“相邻合并”任意两个元素不能跳过其他元素直接合并。合并顺序不同结果代价不同说明存在“最优合并顺序”问题。合并后的对象仍然保持参与合并的资格也就是说子问题天然是连续的区间。能量项链三条全占。每次合并都是相邻两颗珠子变一颗新珠子的头尾标记由两端决定所以合并过程不论怎么安排最终都可以画成一棵二叉树叶子是原始珠子内部节点是一次合并根节点是最后那颗珠子。区间DP实际上就是在枚举这棵二叉树的所有形态选择最优的那棵。有了这个视角就不会被题目是“环”还是“链”带偏因为二叉树结构在环上依然成立只是根节点的位置可能不同。2. dp[l][r]与k转移方程里三个下标是怎么来的2.1 状态定义dp[l][r]代表什么定义dp[l][r]为把区间[l, r]内的珠子按顺序合并成一颗珠子能得到的最大能量。注意这里的“珠子编号”必须是在一条链上的顺序。环形问题处理方式后面再讲先假设我们已经把环剪开成一条链。为什么要这样定义因为合并操作只发生在相邻元素之间所以任何一次合并对应的原始元素集合一定是一个连续区间。这个区间里的珠子不管内部怎么合并最后的结果都是“一颗珠子”而这颗珠子也有头标记和尾标记头标记是a[l]因为最左边的珠子是l它的头标记不会被丢掉。尾标记是a[r1]因为第r颗珠子的尾标记是a[r1]。这个性质非常重要。也就是说dp[l][r]不仅代表一个最大值还隐含地确定了最终那颗珠子的头尾标记。当我们要把两个子区间合并起来时新珠子的头尾标记是自动确定的不需要额外记录。2.2 分割点k最后一次合并发生在哪假设我们把区间[l, r]的珠子合并到最后一颗之前一定存在一个分割点k使得左半部分[l, k]以内先合并成一颗珠子右半部分[k1, r]先合并成一颗珠子最后把这两颗珠子合并成整颗。那么整体最大能量就是dp[l][k] dp[k1][r] 最后那一次合并产生的能量现在的问题只剩下最后一次合并的能量怎么算。2.3 三个下标a[l]、a[k1]、a[r1]的完整推导先看左半部分合并出的那颗珠子头标记是a[l]尾标记是a[k1]再来看右半部分合并出的珠子头标记是a[k1]因为右区间的第一颗珠子是k1它的头标记就是a[k1]尾标记是a[r1]把左右两颗珠子合并时能量公式是“左珠子的头标记 × 左珠子的尾标记同时也是右珠子的头标记 × 右珠子的尾标记”也就是a[l] × a[k1] × a[r1]这个式子三个下标各有各的含义不要死记硬背a[l]左区间最左侧珠子的头标记也就是整颗新珠子的头。a[k1]左右两颗珠子衔接处的标记同时也是左珠子的尾标记、右珠子的头标记。a[r1]右区间最右侧珠子的尾标记也就是整颗新珠子的尾。所以转移方程就是dp[l][r] max(dp[l][r], dp[l][k] dp[k1][r] a[l] * a[k1] * a[r1])注意k的范围是l到r-1。当kl时左边只有一颗珠子dp[l][l]0当kr-1时右边只有一颗珠子dp[r][r]0。这两种情况都是合法的。我这里列一个常见错误对照表都是实际写代码时容易犯的错误写法出错原因正确理解a[l] * a[r] * a[k]三因子选错必须是最左标记、分割点标记、最右外围标记a[l] * a[k] * a[r1]分割点少1衔接处标记是a[k1]不是a[k]a[l] * a[k1] * a[k2]右端错位右端是区间最右珠子的尾标记a[r1]2.4 验证一个小例子为什么这样转移自洽取一个极小的区间[l, r] [1, 3]三颗珠子头标记分别是a[1]、a[2]、a[3]。如果我们先合并珠子2和3再合并珠子1和新的珠子也就是k1左半[1,1]合并后是珠子1头a[1]尾a[2]。右半[2,3]合并后是一颗新珠子头a[2]尾a[4]。最后一次合并能量为a[1] × a[2] × a[4]。这个结果和直接按顺序先合并1、2再合并得到的大珠子、再合并3的方案显然不同。k枚举了两侧内部不同的合并结果之后dp[l][r]自然取到最优。如果换一种理解方式可以把a数组看成一个闭合的标号环a[1], a[2], ..., a[n], a[n1]a[1]。每一次合并就是在标号环上取三个连续的标号相乘然后把中间那个标号去掉。这个视角在后面讲环形处理时会很有用。3. 环形区间翻倍数组处理与断点枚举3.1 为什么环不能直接当链做原题的珠子是环形的第n颗珠子和第1颗珠子相邻。如果直接把数组当直线链做DP合并第n颗和第1颗的这种情况就被排除在外了答案一定是错的。有两种主流处理方式枚举断点把环在某个位置切开枚举N种断点每一种当作一条链做完整DP最后取所有结果的最大值。复制数组把a[1..n]复制一份接到后面变成a[1..2n]然后用区间长度不超过n的链式DP去做最后取长度为n的所有区间最大值。复制数组是更推荐的做法。它本质上同时覆盖了N种断点方案代码改动量小不容易出错。枚举断点需要做N次DP每次都要重新初始化dp数组代码更繁琐时间复杂度也变成N倍虽然在这个题里N100差不了多少但复制数组的写法更优雅也更适合以后扩展到其他环形DP题目。3.2 复制数组的具体操作在读入a[1]到a[n]之后执行一步for (int i 1; i n; i) a[i n] a[i];这样的话原数组从第1个到第n个是原始顺序第n1个到第2n个是原始顺序再来一遍。任何长度为n的连续子区间a[l..ln-1]当l从1取到n时都正好对应环上的一种“剪开”方式。数组大小至少要开到2n2建议直接开205因为题目边界N1002n2202。3.3 区间长度上限仍然是n而不是2n这一点特别容易搞混。复制数组后我们可能会下意识地对所有长度小于等于2n的区间做DP但这是错的。因为题目最终要求的是“把所有珠子合并成一颗”一共只有n颗珠子所以任何有效区间长度最大只能是n。长度超过n的区间意味着把某些珠子算了两遍完全没有意义。因此外层循环len的取值范围是2到n不是2到2n。3.4 最终答案从n个起点中取最大值做完所有长度不超过n的区间DP后答案就是max(dp[1][n], dp[2][n1], ..., dp[n][2n-1])写成代码就是long long ans 0; for (int l 1; l n; l) { ans max(ans, dp[l][l n - 1]); } cout ans endl;这里取l1到n就够了吗确实够。因为环上有n种剪开方式l1到n正好对应n种。ln1时区间是[n1, 2n]它对应的剪开位置和第1种在本质上是一样的只是所有珠子编号平移了一圈答案不会产生新的最优解。一个小细节复制数组后lenn时l的范围会算到n1也就是dp[n1][2n]这种区间。计算它没有问题因为a[n1]就是a[1]它等价于原始的dp[1][n]。但最终统计答案时统计1到n的起点就够了不会漏。4. 递推顺序、边界初始化与完整代码实现4.1 为什么必须先枚举区间长度而不是先枚举左右端点这是区间DP里新手最容易翻车的点。如果你写成for (int l 1; l n; l) { for (int r l 1; r n; r) { // 转移 } }那么先算出来的是所有以l1开头的区间。可是计算dp[1][4]的时候需要用到dp[2][4]这样的子区间而dp[2][4]要等到l2那一轮才能算出来。顺序反了结果就是子问题还没算完就去用得到的答案一定是错的。区间DP的正确循环顺序是先枚举区间长度len。再枚举左端点l右端点r由llen-1确定。最后枚举分割点k。因为长度为len的区间依赖的所有子区间长度都小于len而长度小的区间已经被更早的轮次算完了。这样就保证了每个子问题在需要时都已经就绪。这个道理我在辅导别人时经常用一句话概括区间DP的循环顺序由“状态依赖图”决定不是想怎么写就怎么写。先长度后起点的顺序本质上是在按拓扑序计算。4.2 初始化细节dp数组是全局变量时默认是0。这道题要求最大值而且所有代谢能量都是正整数所以初始化为0是合理的。因为dp[l][l]0表示单颗珠子不需要合并其他未计算的区间从0开始被max更新最终不会出现负数污染答案的情况。但如果题目改成求最小值或者数据里可能出现负数那就必须把dp数组初始化为一个很大的数比如0x3f3f3f3f再把dp[l][l]单独设为0。还有一个边界细节复制数组后dp数组的二维大小也要足以覆盖2n左右的下标范围否则会越界。4.3 完整C代码#include bits/stdc.h using namespace std; const int MAXN 205; int a[MAXN]; long long dp[MAXN][MAXN]; int main() { int n; cin n; for (int i 1; i n; i) { cin a[i]; } for (int i 1; i n; i) { a[i n] a[i]; } for (int len 2; len n; len) { for (int l 1; l len - 1 2 * n; l) { int r l len - 1; for (int k l; k r; k) { long long val dp[l][k] dp[k 1][r] 1LL * a[l] * a[k 1] * a[r 1]; if (val dp[l][r]) dp[l][r] val; } } } long long ans 0; for (int l 1; l n; l) { ans max(ans, dp[l][l n - 1]); } cout ans endl; return 0; }有一点值得说明这里用1LL乘是为了把a[l] * a[k1] * a[r1]提升为long long运算。三个数最大都是100左右乘起来是百万量级但能量累加后可能超过int范围所以dp用long long中间乘法也要用long long否则可能溢出。4.4 复杂度分析三层循环的复杂度很好算长度len从2到n共O(n)种。左端点l最多O(n)个。分割点k最多O(n)个。所以总复杂度O(n^3)空间复杂度O(n^2)。题目N100时实际计算量只有几十万到百万级别即使加上复制数组带来的常数也完全不会超时。这也是区间DP的一个典型特征O(n^3)看起来很吓人但数据范围通常设计成只有几百。4.5 用暴力对拍验证DP的正确性我在自己验证这道题的时候用过最笨的办法写一个递归暴力枚举所有可能的合并顺序。虽然暴力复杂度接近阶乘但n小到6或7时完全可行用来跟DP结果对拍能有效避免方程写错。暴力的思路是用一个数组表示当前剩余的珠子。每次枚举相邻两颗珠子进行合并累加能量。递归到只剩一颗时更新全局最大值。这个暴力代码不需要关注环形问题只要在初始化时把n颗珠子按环的顺序放进数组即可。对拍时随机生成几组小数据对比暴力和区间DP的答案一旦不一致就说明转移方程或者循环顺序有bug。顺便说一句对拍到DP题来说是非常实用的工程习惯。很多选手比赛时只测样例样例过了就交结果挂掉。学会构造小数据、写暴力验证能在赛前把错误提前暴露出来。5. 从能量项链延伸到矩阵链乘比照与优化误区5.1 矩阵链乘和能量项链的本质同构矩阵链乘的经典问题是给定n个矩阵相邻矩阵可以相乘求最少的乘法次数。它的转移是dp[l][r] min(dp[l][k] dp[k1][r] p[l-1] * p[k] * p[r])其中p是矩阵的维度序列。把能量项链的转移和矩阵链乘放在一起对比项目能量项链矩阵链乘输入标记序列a[1..n]a[n1]a[1]p[0..n]合并代价a[l] * a[k1] * a[r1]p[l-1] * p[k] * p[r]目标最大化总能量最小化乘法次数子问题珠子数lenlen初始值00或INF两者唯一本质区别就是环与链矩阵链乘的矩阵顺序是固定的直线链而能量项链的珠子顺序是一个闭合环。所以能量项链完全可以看成“环形矩阵链乘”。记住这个同构关系你在做别的题目时就有了一个检索索引只要看到合并代价是“两端的标记乘中间标记”就能立刻联想到矩阵链乘和能量项链。5.2 四边形不等式优化能不能套这题不能盲目用很多人学到区间DP后会听说明“四边形不等式可以把O(n^3)优化到O(n^2)”于是想把能量项链也优化一下。但这里必须泼一盆冷水能量项链的代价函数a[l] * a[k1] * a[r1]未必满足四边形不等式也不能保证决策单调性。盲目套四边形不等式优化的结果是可能得到错误答案。这个陷阱我在自己学习过程中也踩过。当时看到别人在石子合并题里用四边形不等式优化跑得飞快就想照搬到能量项链上结果样例都过不了后来去分析代价函数才发现问题。怎么做才是安全的如果你确实想让这段优化代码生效有两个方向先证明代价函数满足四边形不等式或最优决策单调性再套优化。用O(n^3)的普通区间DP先对拍验证优化版本的结果。以能量项链的规模O(n^3)已经足够完全没必要冒这个险。我个人建议是竞赛中除非题目N到1000以上而且你非常确定可以优化否则老老实实写完整DP是更稳的选择。5.3 记忆化搜索版本绕开递推顺序的另一种写法递推版需要严格按长度从小到大循环很多人总是记不住这个顺序。记忆化搜索或者说递归DP可以绕开这个麻烦因为递归天然只会去计算尚未计算的子状态天然满足依赖顺序。对应的记忆化搜索代码如下#include bits/stdc.h using namespace std; const int MAXN 205; int n; int a[MAXN]; long long dp[MAXN][MAXN]; bool vis[MAXN][MAXN]; long long dfs(int l, int r) { if (l r) return 0; if (vis[l][r]) return dp[l][r]; vis[l][r] true; for (int k l; k r; k) { dp[l][r] max(dp[l][r], dfs(l, k) dfs(k 1, r) 1LL * a[l] * a[k 1] * a[r 1]); } return dp[l][r]; } int main() { cin n; for (int i 1; i n; i) cin a[i]; for (int i 1; i n; i) a[i n] a[i]; long long ans 0; for (int l 1; l n; l) { ans max(ans, dfs(l, l n - 1)); } cout ans endl; return 0; }这段代码的优势在于转移方程和递推版一模一样但不需要考虑循环顺序。缺点是递归调用有一定开销不过N100时完全没有压力。新手如果对循环顺序不熟可以先用记忆化搜索版本理解状态设计再回头写递推版。5.4 相关变体这些题都是同一张脸区间DP有一批经典变体原理几乎一致石子合并合并相邻两堆石子代价是总重量环形版本同样需要翻倍数组。凸多边形划分把凸多边形划分成三角形求最小代价转移和矩阵链乘几乎一样。多边形游戏顶点和边上都有权每次删除一条边合并两个顶点并计算权值也是环形区间DP。它们的通用模板都是dp[l][r] max/min(dp[l][k] dp[k1][r] cost(l, k, r))区别只在cost函数。所以每当你遇到一个新的合并类题目先确定cost是什么然后照抄区间DP的框架大概率就能写出正确解法。6. 面向考场的实践心得对拍、调试与时间分配6.1 拿到题目之后先强制自己回答三个问题不管题目包装得多花哨我都会先问自己三个问题这个合并操作是不是只能作用于相邻元素合并代价由哪些端点值决定可不可以写成一个关于l、k、r的三元表达式有没有环结构源数组要不要翻倍如果前两个问题的答案都是“是”那基本可以确定是区间DP框架。第三个问题决定边界怎么写。这个流程虽然简单但能避免你在考场上花大量时间在错误的套路上。6.2 调试技巧打印dp表比空想要有效万一代码跑出错误答案我最常用的调试方式是把dp表的上三角区域打印出来重点观察len2的区间即相邻两颗珠子合并的能量是否和手算一致。len3的区间是否取到了两种分割方式中的最大值。最终答案对应的是哪个l有没有覆盖所有起点。这些数据能很快暴露出转移方程的哪一项写错。比如我曾经花很久查一个bug最后发现是转移里把a[r1]写成了a[r]打印dp表后一眼就看出len2的区间都少了最后一个因子。6.3 考场上的时间分配建议区间DP题目的实现速度很大程度上取决于平时对模板的熟练度。我建议这类题的做题节奏是前10分钟确认题意、状态定义、转移方程最好先在纸上写出dp[l][r]的表达式。中间10分钟写代码注意数组大小、long long、环形复制。最后10分钟构造至少一组手写小数据或者直接跑暴力对拍。如果你能把能量项链这道题练到“看到题目直接默写代码”的程度那么在正式比赛中遇到同类型的题你会节省出大量时间留给更难的关卡。6.4 我个人的一点实际体会这类合并型DP题本质上是在枚举所有可能的二叉树形态。你不需要每一次合并都去模拟具体操作只需要从“最后一次合并发生在哪里”这个角度去拆分区间。能量项链作为NOIP 2006的线题被无数选手刷过也坑过无数人但它绝对值得反复写几遍因为它把区间DP最核心的“子区间划分”“代价函数推导”“环转链”三个考点一次性全练到了。我见过不少同学考前还在死背模板遇到变化就头晕。其实只要从这道题出发把“为什么这样转移”和“为什么这样枚举”彻底想清楚后面再做石子合并、多边形切割之类的变体都会顺畅很多。这也是我写这篇东西的初衷。