【 例 1】石子合并（信息学奥赛一本通- P1569）

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：

1、选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。

2、选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

输入第一行一个整数 n，表示有 n 堆石子。

第二行 n 个整数，表示每堆石子的数量。

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

数据范围与提示：

对于 100% 的数据，有 1≤n≤200。

在动态规划的学习路径上，“石子合并”是一道绕不开的经典题。

如果是“一排”石子，相信大家闭着眼都能写出状态转移方程。但如果题目稍微变一下，把石子摆成“一圈”（圆形操场），很多同学就慌了：首尾相接了，这区间怎么定？数组怎么开？

今天我们就来彻底解决这个问题，掌握解决环形 DP 问题的核心技巧——断环成链。

1. 问题背景

题目描述：

有N堆石子摆成一个圆环，每次只能合并相邻的两堆，合并的得分是两堆石子数量之和。

求：

1. 将这N堆石子合并成一堆的最小得分。

2. 将这N堆石子合并成一堆的最大得分。

数据范围：。

2. 算法分析：断环成链

核心痛点

普通的区间DP依赖于线性的数组下标[1, N]。但在环形结构中，第N堆和第1堆也是相邻的，如果我们强行在圆上做DP，下标处理会非常麻烦（涉及取模运算），而且难以枚举所有可能的“切断点”。

解决方案

我们可以使用“断环成链”的技巧：

1. 复制数组：将长度为N的原数组A，复制一份接在末尾，变成长度为2N的新数组。

2. 化圆为线：在这个长为2N的数组上，任意截取一段长度为N的子数组，都对应原圆环的一种“断开”方式。

图解示例：

假设N=3，石子为[4, 5, 9]。

复制后变成：[4, 5, 9, 4, 5, 9]。

• 区间[1, 3](4,5,9) 对应原环（以 9-4 之间断开）。

• 区间[2, 4](5,9,4) 对应原环（以 4-5 之间断开）。

• 区间[3, 5](9,4,5) 对应原环（以 5-9 之间断开）。

这样，我们就把一个复杂的环形问题，转化为了在2N长度的数组上求解长度为N的区间 DP 问题。

状态定义

我们定义两个数组：

• dp1[i][j]：合并第i到第j堆石子的最小代价。

• dp2[i][j]：合并第i到第j堆石子的最大代价。

状态转移方程

这与普通石子合并完全一致：

枚举分割点k ()：

dp1[i][j] =

dp2[i][j] =

其中使用前缀和S在O(1)时间内求出：S[j] - S[i-1]。

3. 完整代码

//圆形排放，就把n堆石子复制一遍加到末尾，就可以化环为链去解决 #include <iostream> #include <algorithm>//对应min max #include <cstring>//对应memset using namespace std; int a[420];//存每堆石子多少个 数组开2倍大小 int dp1[420][420];//dp1[i][j]代表合并i到j的最小得分总和 int dp2[420][420];//dp2[i][j]代表合并i到j的最大得分总和 int s[420];//求前缀和 int main(){ //求最小得分总和就初始化dp1为无穷大 memset(dp1,0x3f,sizeof(dp1)); //求最大得分总和就初始化dp2为0 memset(dp2,0,sizeof(dp2)); int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; //圆形排放，就把n堆石子复制一遍加到末尾，就可以化环为链去解决 a[i+n]=a[i]; } n=n*2;//链长度 //自己合并自己得分为0 for(int i=1;i<=n;i++){ dp1[i][i]=0; dp2[i][i]=0; } //求前缀和 for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; //从小到大枚举区间长度 大区间总是由小区间构成 for(int len=2;len<=n/2;len++){ //枚举左端点位置 for(int i=1;i<=n-len+1;i++){ int j=i+len-1;//右端点 for(int k=i;k<j;k++){//枚举分割点 //自身得分与产生左区间得分+产生右区间得分+左右区间合并得分比大小 //s[j]-s[i-1]是本次合并的得分 dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+s[j]-s[i-1]); dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+s[j]-s[i-1]); } } } //统计答案，答案不一定是dp[1][N]，而是所有长度为N的区间中的最优值 int ma=0; int mi=0x3f3f3f3f; for(int i=1;i<=n/2;i++){ mi=min(mi,dp1[i][i+n/2-1]); ma=max(ma,dp2[i][i+n/2-1]); } cout<<mi<<endl<<ma; return 0; }

4. 易错点与总结

1. 数组大小要翻倍：

   因为我们把数组复制了一遍，长度变成了2N，所以数组大小必须开到400以上（题目）。如果只开200会越界。

2. 循环边界优化：

   第一层循环枚举len时，虽然链的总长是2N，但我们最终只需要长度为N的结果。所以len循环到n(即N) 就可以停止了，这样可以节省一半的计算时间。

3. 答案统计方式：

   普通石子合并的答案是dp[1][n]。

   但环形问题的答案，是需要在2N的链上，遍历所有长度为N的区间，取其中的最大值/最小值。即遍历i从1到N，取dp[i][i+N-1]。

4. 初始化细节：

   求min时memset用0x3f，求max时用0。且dp[i][i]（自己合并自己）代价必须显式设为 0，否则无穷大会导致结果错误。

总结：

以后遇到“环形”问题（如环形强盗抢劫、环形最大子数组和），第一时间想到“复制数组、断环成链”，这个技巧是通用的。