区间动态规划：石子合并问题的深度解析与实现

核心逻辑与数学原理

区间动态规划（Interval DP）是研究线性序列上局部区间合并与演变的标准模型。其核心本质是以区间长度（Scale）作为阶段进行拓扑推进，在小区间状态完全固化后，通过枚举区间内部的割点，向大区间进行状态贡献。

石子合并（Stone Merging）是区间 DP 的教科书级模型。给定一排 $N$ 堆石子，每次只能合并相邻的两堆，合并的代价为两堆石子的重量之和。求将所有石子合并为一堆的最小或最大总代价。

区间 DP 的数学合规性由以下底层逻辑支撑：

阶段的非线性划分：传统线性 DP 按照序列下标 $i$ 从 1 到 $N$ 逐个推进。而区间 DP 的“阶段”是区间的长度 $len$。只有当所有长度为 $len-1$ 的子区间全部计算完毕并固化，才能开始计算长度为 $len$ 的区间。
决策的分割点（Cut Point）映射：对于任意一个闭区间 $[l, r]$，它化归为一堆的最后一步，必然是由某两个更小的相邻子区间 $[l, k]$ 和 $[k+1, r]$ 合并而来。通过枚举分割点 $k \\in [l, r-1]$，可以穷举出所有可能的最后一步决策。
区间性质的加和性（前缀和优化）：合并区间 $[l, r]$ 时产生的单步直接代价，恰好是该区间内所有原始元素的权值之和。为了规避 $O(N)$ 暴力累加区间和，必须引入前缀和数组 $S$，在 $O(1)$ 时间内输出区间权值和：$W(l, r) = S[r] - S[l-1]$。

状态设计与算法推导

1. 状态空间定义

设状态 $f[l][r]$ 表示将区间 $[l, r]$ 内的所有石子合并为一堆的最小代价。

2. 状态转移方程推导

任何大区间 $[l, r]$ 都是由两部分子区间合并而来，其总代价等于：左区间的合并代价 + 右区间的合并代价 + 本次合并的直接代价。

$$f[l][r] = \min_{l \le k < r} \{ f[l][k] + f[k+1][r] \} + W(l, r)$$

其中 $W(l, r) = \sum_{i=l}^{r} A[i] = S[r] - S[l-1]$。

3. $O(N^3)$ 标准循环格式与拓扑序

为了确保在计算 $f[l][r]$ 时，等号右边的 $f[l][k]$ 和 $f[k+1][r]$ 已经是最优解，必须严格控制三层循环的物理嵌套顺序：

外层循环：枚举区间长度 $len$（从 2 到 $N$）。
中层循环：枚举区间的左端点 $l$，并动态计算出右端点 $r = l + len - 1$。
内层循环：枚举分割点 $k$（从 $l$ 到 $r-1$）。

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

以下源码为石子合并（求最小代价与最大代价）的标准区间 DP 实现，严格通过 Linux g++ -O2 编译规范。

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

using namespace std;

const int MAXN = 305;
const int INF = 0x3f3f3f3f;

int a[MAXN];
int s[MAXN]; // 前缀和数组
int f_min[MAXN][MAXN];
int f_max[MAXN][MAXN];

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

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

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i]; // 预处理前缀和，O(1) 获取区间重量和
    }

    // 初始化边界：长度为 1 的区间合并代价为 0，其余初始化为极值
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) {
                f_min[i][j] = 0;
                f_max[i][j] = 0;
            } else {
                f_min[i][j] = INF;
                f_max[i][j] = -INF;
            }
        }
    }

    // 严格按照区间 DP 标准三层格式进行拓扑遍历
    // 致命踩坑点：外层循环必须是区间长度 len！
    for (int len = 2; len <= n; ++len) { 
        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);
                f_max[l][r] = max(f_max[l][r], f_max[l][k] + f_max[k + 1][r] + score);
            }
        }
    }

    cout << f_min[1][n] << "\n" << f_max[1][n] << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 错误地将 $l$ 和 $r$ 作为前两层循环

现象：写出了类似 for (int l = 1; l <= n; ++l) for (int r = l; r <= n; ++r) 的双重循环结构，内层再枚举 $k$。这会导致计算 $f[l][r]$ 时，它所依赖的右侧子区间 $f[k+1][r]$ 此时根本还没有被计算出来（其值依然是初始化的 INF），从而导致整张状态网格转移逻辑彻底瘫痪。
规避手段：区间 DP 必须强制遵守“长度 $ o$ 左端点 $ o$ 决策点”或“左端点（倒序） $ o$ 右端点 $ o$ 决策点”的循环顺序。牢记只有当短区间全部固化，长区间才有资格求值。

2. 忽略长度为 1 的区间初始值设置

现象：未将 $f[i][i]$ 显式初始化为 0，或者在对 f_min 进行 memset(f_min, 0x3f, sizeof(f_min)) 后，忘记恢复 $f[i][i] = 0$。这会导致在计算长度为 2 的区间 $f[l][l+1] = f[l][l] + f[l+1][l+1] + W$ 时，直接加上了两个 INF，导致最终结果全面输出伪极大值。
规避手段：写完状态初始化后，必须肉眼确认基础元状态（即长度为 1 的叶子节点）的数值符合物理现实（合并自己不需要代价，故必为 0）。

经典 NOIP/洛谷真题

1. 洛谷 P1775 石子合并（弱化版）

题意描述：设有 $N$ 堆石子排成一排，其编号为 $1, 2, 3, \dots, N$。每堆石子有一定的质量。现要将这 $N$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为两堆石子的质量之和。求最小的总代价。
问题本质与解题思路：标准的区间动态规划模型，即上文推导的最小代价版本。
核心思路：直接套用 $O(N^3)$ 的标准循环模板。利用前缀和进行区间价值求和优化。由于该弱化版 $N \le 300$，三重循环的总运算量在 $2.7 \times 10^7$ 左右，Linux 环境下耗时小于 0.05 秒，轻松通关。

2. 洛谷 P3143 [USACO16OPEN] Diamond Collector S

题意描述：给定 $N$ 个正整数，要求从中选出两组数，每组内部的最大值与最小值的差值不能超过 $K$。两组数不能有重叠的元素（即每个位置的数至多选一次）。求两组数最多能包含多少个数字。
问题本质与解题思路：线性区间最值覆盖与双区间不重叠组合问题。
核心思路：首先对原始数组进行升序排序，使具有相似数值的元素在空间上连续。接着，通过双指针（滑动窗口）可以预处理出以每个位置 $i$ 为左端点、满足差值 $\le K$ 的最远右端点，从而得到每个局部合法的区间长度。
区间 DP 降维融合：设 $L[i]$ 表示区间 $[1, i]$ 内能够选出的单组最大数量，$R[i]$ 表示区间 $[i, N]$ 内能够选出的单组最大数量。它们分别可以通过单向线性扫描（本质上是区间最大值的递推）求得。最终，枚举切分点 $i$，全局最大数量即为 $\max_{1 \le i < N} \{ L[i] + R[i+1] \}$。通过区间独立性的解析，规避了暴力枚举双区间导致的 $O(N^2)$ 复杂度。