环形区间 DP
断环为链·能量项链
本课摘要
环形区间 DP课程回答“环形区间怎样通过复制序列转化为链形区间”。内容以断环为链·能量项链为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。
- 判断环形区间 DP的适用条件与状态边界
- 围绕“断环为链·能量项链”推导转移与计算顺序
- 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节
正在整理目录…
当石子摆成一个环
上一节的石子排成一条链：两端是「头」和「尾」，谁也不挨着谁。可石子合并的原题（P1880）里，石子其实摆成一个环——第 堆与第 堆也相邻，也能合并。规则不变：每次并相邻两堆、代价为两堆之和，直到剩一堆，求最小（或最大）总代价。
差别虽小，却不能直接照搬链形。链形 默认最后剩下的那堆断在第 堆左侧；但在环上，「最后剩的那堆从哪里断开」是自由的——可以从任意一堆起、绕一圈回来。以 为例：当成直链算得 ；可若允许「先并第 3 堆与第 0 堆」（环上它们相邻），从第 堆起绕一圈只需 。那条多出来的边，能让合并更省。
也别想着「枚举每个断点，各跑一遍链形 DP」——那要跑 遍、白白多花一个 倍。有没有办法一次把所有断法都算进去？有，而且极简洁：断环为链。
断环为链：复制一倍，环上任一圈都成了链上一段
核心一招：把石子数组复制一倍，首尾拼成一条长度 的链，其中 。这样一来，环上从任意堆起、绕一整圈的那 堆，在这条 链里都恰好是一段连续区间 。原本「绕过尾首」的麻烦相邻边，被复制的那半段抹平成了普通的链内相邻。
于是环形问题被化归成链形：在 上跑一模一样的区间三角表（状态、转移、按长度递推，全部照搬上一节），只是网格从 变成 ：
算完之后，环形答案不是某一格，而是枚举所有起点 ，在这 个「整圈窗口」里取最优：
为什么长度只需枚举到 、窗口长度恰取 ？因为一整圈正好 堆：长度小于 合不完，长度大于 会让某堆被数两次（既在原段、又在复制段），非法。取 就把 换成 ，一字不改。
本质
环形区间 DP = 链形区间 DP + 一层「断点」枚举，而这层枚举被「复制一倍成 链」悄悄吸收进了同一张三角表里。诀窍在于：环上任一条连续弧，在 链上都能找到一段等价的连续区间——于是「从哪里断」不必外层重复跑，只需最后在 个长度为 的窗口里取最优。复杂度仍是三层循环，。
跟着算一遍：a=[3,9,3,4] 的那个更省的窗口
仍用 。复制一倍得 （下标 ），前缀和 。答案落在起点 的窗口 （对应 ，即环上从第 1 堆绕一圈）。把这个窗口按长度算出来：
看 2n 链的三角表长出来
- 来源参与当前转移的依赖状态
- 当前正在计算或观察的状态
- 确定 / 最优已进入当前最优解或确定结果
- 已处理已经扫描、当前不再活跃的状态
- 非法越界、冲突或不可达状态
为什么要枚举窗口：一张图看断点如何平移
断环为链的几何直觉是： 个「整圈窗口」 在 链上逐格右移，每一个对应「从某堆断开」的一种合并方案。它们覆盖的都是环上同一圈的 堆，只是起止不同——所以答案要在它们之间取最优，缺一不可。
记死这套「复制一倍 + 三层循环 + 扫窗」骨架——几乎所有环形合并/区间题都用它：
for i = 0 … n-1: a2[i+n] = a[i] // ★复制一倍，链长 2n
for 长度 len = 2 … n: // 只需到 n（一整圈）
for 左端点 l = 0 … 2n-len:
r = l + len - 1
for 分割点 k = l … r-1:
dp[l][r] = min( dp[l][r], dp[l][k] + dp[k+1][r] + sum(a2[l..r]) )
ans = min over i∈[0,n-1] of dp[i][i+n-1] // ★扫 n 个整圈窗口取优换个断点，窗口就平移：环↔链展开
上面是「填表」视角；再换个「展开」视角把直觉坐实。下面的互动让你亲手选断点：环从那里剪开、展成 直链，对应的长度 窗口随之在链上整体平移。切几个断点，感受「同一圈、不同起止」，以及为何单看一个 会漏掉更优解。
两个常见坑
其一，长度别超过 。在 链上若枚举到长度 的区间，会把某堆石子数两遍，答案偏大且无意义——外层 只跑到 即可。
其二，取 时下三角别参与、初值要设对。 初值 、 初值 ，且只在合法上三角（）转移。若像能量项链那样代价可能为负（如三元乘积含负数），求最小时还要留意「负负得正」，别漏候选。
例题
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[205]; // ★断环为链：a[i] 与 a[i+n] 同值，链长 2n
int pre[205]; // 前缀和，sum(l..r) = pre[r] - pre[l-1]
int f[205][205]; // 最小合并代价
int g[205][205]; // 最大合并代价
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i + n] = a[i]; // ★复制一倍，接成长度 2n 的链
}
for (int i = 1; i <= 2 * n; i++)
pre[i] = pre[i - 1] + a[i];
for (int len = 2; len <= n; len++) // 区间长度只需到 n（一整圈）
for (int l = 1; l + len - 1 <= 2 * n; l++)
{
int r = l + len - 1;
int s = pre[r] - pre[l - 1]; // 本区间合并追加的代价
f[l][r] = INF;
g[l][r] = -INF;
for (int k = l; k <= r - 1; k++) // 枚举分割点 k
{
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s);
}
}
int mn = INF, mx = -INF;
for (int i = 1; i <= n; i++) // ★枚举 n 个长度为 n 的窗口
{
mn = min(mn, f[i][i + n - 1]);
mx = max(mx, g[i][i + n - 1]);
}
cout << mn << endl; // 一题双问：最小、最大
cout << mx << endl;
return 0;
}#include <iostream>
using namespace std;
int e[205]; // 珠子上的标记值，断环为链后长 2n
long long f[205][205]; // f[i][j]：把标记 i..j 之间的珠子合成一颗的最大释放能量
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> e[i];
e[i + n] = e[i]; // ★复制一倍
}
long long ans = 0;
for (int len = 2; len <= n; len++) // len = 相邻标记跨度，含 len 个原珠首尾标记
for (int i = 1; i + len <= 2 * n; i++)
{
int j = i + len; // 合成后新珠的两端标记 e[i]、e[j]
for (int k = i + 1; k < j; k++) // 枚举最后一次并珠处的中间标记 k
{
long long v = f[i][k] + f[k][j] + (long long)e[i] * e[k] * e[j];
f[i][j] = max(f[i][j], v); // ★最后一并释放 head*mid*tail
}
if (len == n) // 一整圈：更新答案
ans = max(ans, f[i][j]);
}
cout << ans << endl;
return 0;
}