环形动态规划技术详解：破环成链与断边转换

核心逻辑与数学原理

环形动态规划的本质是处理拓扑结构上的首尾连通性。在普通的线性序列中，位置 $1$ 和位置 $N$ 是割裂的边界；而在环形结构中，位置 $1$ 和位置 $N$ 之间存在一条等价的有向边，导致状态空间在几何上闭合。

处理环形拓扑，主流有两种硬核的降维映射技术：

1. 破环成链（倍长序列 / Doubling Method）：

   • 几何映射：将原长度为 $M$ 的环形序列复制一份，拼接在原序列末尾，形成一个长度为 $2M$ 的线性序列：$A[1 \text{ to } 2M]$。
   • 逻辑等价性：原环形结构中的任意一个长度为 $M$ 的连续段，在倍长后的线性序列中，都能唯一对应一个区间 $[l, l + M - 1]$（其中 $1 \text{ ≤ } l \text{ ≤ } M$）。
   • 适用场景：区间 DP、滑动窗口等需要显式枚举环上所有可能连续子区间的模型。

2. 断边转换为多次 DP（Boundary Fixing）：

   • 几何映射：显式切断位置 $1$ 与位置 $M$ 之间的环形边，使其退化为线性结构。为了强行闭合首尾限制，需要通过“强制施加边界条件”进行两次或多次独立的线性 DP。
   • 逻辑等价性：对于首尾相邻的限制（如“相邻两个位置不能同时选”），要么位置 $1$ 不选（此时位置 $M$ 选不选无所谓），要么位置 $1$ 必选（此时位置 $M$ 强制不能选）。这两种边界条件完全穷举了首尾相连的所有合法拓扑状态。
   • 适用场景：树形 DP、线性序列选择问题（如环形不相邻最大子集）。

状态设计与算法推导

以经典的“环形石子合并”与“环形抢劫（不相邻最大子集）”为例，拆解状态推导。

1. 环形区间 DP（破环成链）

• 状态设计：设 $f[l][r]$ 表示倍长序列中，合并区间 $[l, r]$ 的最小代价。
• 转移方程：

$$f[l][r] = \min_{l \text{ ≤ } k < r} \bigg\{ f[l][k] + f[k+1][r] \bigg\} + (S[r] - S[l-1])$$

其中前缀和数组 $S$ 必须预处理到 $2M$ 的边界。

• 目标答案：

$$\text{Ans} = \min_{1 \text{ ≤ } l \text{ ≤ } M} \bigg\{ f[l][l + M - 1] \bigg\}$$

2. 环形状态压缩（两次 DP 边界控制）

假定序列长度为 $M$，相邻位置不能同时选。

• 状态设计：$f[i][0/1]$ 表示决策到位置 $i$，当前位置不选(0)或选(1)的最大收益。

• 两次 DP 分支：

  • 分支 A：强制不选位置 $1$。初始化 $f[1][0] = 0, f[1][1] = -\text{INF}$。跑完线性 DP 后，最终答案可能在 $f[M][0]$ 或 $f[M][1]$ 中产生（因为位置 $1$ 没选，位置 $M$ 随意）。
  • 分支 B：强制选位置 $1$。初始化 $f[1][0] = -\text{INF}, f[1][1] = A[1]$。跑完线性 DP 后，最终答案只能在 $f[M][0]$ 中产生（因为位置 $1$ 选了，位置 $M$ 强制不能选）。

• 全局最优解：对两个分支的合法终态取最大值。

C++ 标准源码（NOIP风格）

以下源码在一个程序中，分别给出了环形石子合并（倍长法）与环形不相邻最大收益（两次 DP 法）的完整实现。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 405; // 针对倍长，数组大小必须翻倍 2 * 200 = 400
const int INF = 0x3f3f3f3f;

int a[MAXN];
int s[MAXN];
int f_min[MAXN][MAXN];

// 用于线性 DP 环形切断模型的数组
int v[MAXN];
int dp[MAXN][2];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m;
    if (!(cin >> m)) return 0;

    // ==================== 模型 1: 环形石子合并 (破环成链) ====================
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
        a[i + m] = a[i]; // 核心：倍长序列，将环形映射为双倍长度的链
    }

    int n = 2 * m;
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + a[i]; // 前缀和边界拓展到 2M
    }

    // 区间 DP 初始化
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f_min[i][j] = (i == j) ? 0 : INF;
        }
    }

    // 标准区间 DP 拓扑序递推
    for (int len = 2; len <= m; ++len) { // 致命踩坑点：合并的区间长度上限依然是 M，绝不是 2M！
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            int score = s[r] - s[l - 1];
            for (int k = l; k < r; ++k) {
                f_min[l][r] = min(f_min[l][r], f_min[l][k] + f_min[k + 1][r] + score);
            }
        }
    }

    // 在所有长度为 M 的线性合法区间中横向扫描最小值
    int ans_merge = INF;
    for (int l = 1; l <= m; ++l) {
        ans_merge = min(ans_merge, f_min[l][l + m - 1]);
    }


    // ==================== 模型 2: 环形不相邻最大收益 (两次 DP) ====================
    for (int i = 1; i <= m; ++i) {
        cin >> v[i];
    }

    // ---- 第一次 DP: 强制不选位置 1 ----
    dp[1][0] = 0;
    dp[1][1] = -INF; // 阻断选 1 的可能性
    for (int i = 2; i <= m; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + v[i];
    }
    int res1 = max(dp[m][0], dp[m][1]); // 位置 1 没选，位置 M 可选可不选

    // ---- 第二次 DP: 强制选择位置 1 ----
    dp[1][0] = -INF; // 阻断不选 1 的可能性
    dp[1][1] = v[1];
    for (int i = 2; i <= m; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + v[i];
    }
    int res2 = dp[m][0]; // 致命踩坑点：位置 1 选了，位置 M 强制只能处于不选状态 (0)

    int ans_select = max(res1, res2);

    cout << ans_merge << " " << ans_select << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 破环成链时区间长度 $len$ 的控制越界

• 现象：在使用倍长技术处理环形区间 DP 时，选手误将最外层的区间长度枚举写成了 for (int len = 2; len <= 2 * m; ++len)。这会导致算法试图去计算并合并一个长度超过原环容量的“超级冗余区间”（例如把第 1 堆石子跟复制出来的第 1 堆石子同时合进了一个虚无的答案里），直接引发语义错误与数值爆表。
• 规避手段：序列长度虽然倍长到了 $2M$，但状态转移中的区间长度上限依然是 $M$。倍长只是为了给所有可能的环形切口腾出对齐的空间，并不是要合并 $2M$ 个元素。

2. 两次 DP 断边时终态更新非法重叠

• 现象：在写“强制选位置 1”的第二次 DP 时，最后收集答案直接无脑复制 max(dp[m][0], dp[m][1])。这在环形逻辑上产生了后效性污染：位置 1 和位置 $M$ 此时被同时选中，环形限制形同虚设。
• 规避手段：清晰绘制边界控制矩阵。若起点被强制选定，则终点状态只能由不含起点的状态维（如 dp[m][0]）贡献，切勿遗漏对终态的特判。

经典 NOIP/洛谷 真题

1. 洛谷 P1880 [NOI1995] 石子合并

• 题意描述：在一个圆形操场的四周摆放着 $N$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。求合并后的最小得分与最大得分。
• 问题本质与解题思路：环形区间动态规划的奠基题。
• 核心思路：属于典型的“破环成链”应用模型。通过 $A[i+N] = A[i]$ 将圆环展平成长度为 $2N$ 的直线段。在外层循环 $len \text{ ≤ } N$ 的约束下，计算出二维空间内所有的 f_min[l][r] 和 f_max[l][r]。最终，遍历所有合法的环形断点（即 $l \text{ in } [1, N]$），在 $[l, l+N-1]$ 区间中收集全局的 min 与 max 极值。

2. 洛谷 P6064 [USACO05JAN] Naptime G

• 题意描述：每天有 $N$ 个小时，每小时都有一个特定的恢复活力值 $U_i$。高大上的奶牛每天要睡 $B$ 个小时，这 $B$ 个小时可以分成若干段。有一个核心限制：每段睡眠的第一个小时由于处于准备阶段，无法恢复任何活力。另外，每天的第 $N$ 个小时和下一天的第 1 个小时是连续相邻的（圆环时间轴）。求每天最大能恢复的总活力值。
• 问题本质与解题思路：带有前置损耗状态的环形状态机 DP。
• 状态设计：设 $f[i][j][0/1]$ 表示决策到第 $i$ 个小时，已经睡了 $j$ 个小时，且当前第 $i$ 个小时处于“没睡(0)”或“在睡(1)”的状态。
• 核心思路：时间轴是环形的，意味着第 $N$ 小时如果在睡，第 1 小时就可以直接享受活力恢复（无需准备阶段）。采用“断边转换为多次 DP”的策略：
  1. 第一次 DP：假设第 1 小时没睡或处于准备阶段，初始化 $f[1][1][1] = 0, f[1][0][0] = 0$，其余为 -INF。线性递推到 $N$ 后，最终答案取 $\text{max}(f[N][B][0], f[N][B][1])$。
  2. 第二次 DP：强制第 $N$ 小时和第 1 小时是连续睡眠。也就是说第 1 小时直接进入状态 1 且能收割收益。初始化 $f[1][1][1] = U_1$，其余为 -INF。线性递推到 $N$ 后，为了保证第 $N$ 小时确实和第 1 小时连通，最终答案只能取 f[N][B][1]。 两轮 DP 覆盖了环上状态的所有边际可能性，彻底消除了后效性。