形式化题目

给定长度为 $N$ 的序列 $a_1, a_2, \dots, a_N$。初始时每个元素各成一段，每次操作选择相邻的两段合并成一段，代价为这两段所含元素之和；合并后的新段与原来两段的邻居相邻。

求把所有元素合并成一段所需的最小总代价。

等价说法：每次把相邻的两个连续区间并为一个大区间，代价为合并后区间的元素之和；求把 $[1,N]$ 并成一个区间的最小总代价。

暴力解法

思路

最直白的做法就是照着题意模拟：维护当前局面（若干堆石子排成一排），每一步枚举所有相邻的两堆并合并，递归下去直到只剩一堆，用总代价更新答案。

样例 $a=(1,3,5,2)$ 的全部 $(4-1)!=6$ 种合并顺序如下，括号里是本次合并的两堆及合并后的新堆：

最小值 22 正是样例输出。表里还藏着两条线索：第 1、2 行只是交换了两段内部的先后顺序，总代价完全一样；而换了断点之后，代价从 22 一路涨到 29。

代码

本层只用文字与表格说明朴素做法，不单独给出 brute.cpp：它与正解共用同一套“合并树”语义，差别只在枚举的对象是操作序列还是断点，单独放一份代码文件不会带来新信息。上面那张全顺序表已经能完整复现这一层的全部行为。

复杂度

第 $t$ 步有 $N-t$ 种可选合并，总方案数 $(N-1)!$：

看到 $N=8$ 时还有 5040 种，到 $N=12$ 已经接近 $4\times10^7$，而 $N=300$ 是天文数字：阶乘增长让“把所有顺序试一遍”在任何语言里都不可行。再加上每次模拟还要 $O(N)$ 维护局面，总时间 $O(N!)$ 量级，空间 $O(N)$ 递归栈。

瓶颈

暴力枚举的对象是操作序列，而同一棵合并树可以被写成很多个不同的操作序列（表里前两行就是），这些重复正是浪费的来源；同时序列总数按阶乘增长，$N=300$ 时根本无法枚举。

但表里也有一个决定性的观察：真正决定总代价的是每次合并在哪里断开，也就是最终那棵合并树长什么样，而不是“左右两段谁先合”。

正解

思路

第一步：只看最后一次合并。

把 $a_1..a_N$ 合并成一堆，最后一步必然是：某个断点 $k$ 让左边 $a_1..a_k$ 已经合成一堆、右边 $a_{k+1}..a_N$ 已经合成一堆，再把这两堆合并。

1
2
3
4        [1 . . . . . . . . . . . . N]        代价 += S(1,N)（全段质量之和）
                 /            \
       [1 .. k]                 [k+1 .. N]
        递归求解                 递归求解

这一步的代价是全部质量之和 $S(1,N)$，与 $k$ 无关；而左右两边各自怎么合成那一堆互不影响。于是

枚举断点 $k$ 与枚举整棵合并树是一一对应的，不再有操作序列的重复。

第二步：把子问题编号成区间。

式子里的子问题都形如「把 $a_l..a_r$ 合成一堆」。定义 $f(l,r)$ 为它的最小代价，$S(l,r)=\sum_{t=l}^{r}a_t$，则

第三步：按区间长度递推。

$f(l,r)$ 依赖的 $f(l,k)$ 长度为 $k-l+1$、$f(k+1,r)$ 长度为 $r-k$，两者都严格小于 $r-l+1$。所以按长度从小到大枚举区间，被依赖的值一定已经算好，既不需要记忆化递归，也不需要判“是否算过”。区间和用前缀和 $S(l,r)=ps[r+1]-ps[l]$ 一次取得。

样例 $a=(1,3,5,2)$ 的分层结果（下标采用 main.py 的 0 基：$i=0$ 对应题面的第 1 堆；行 = 区间长度 $L$，列 = 起点 $i$，单元格 = $f(i,i+L-1)$；— 表示该长度下没有这个起点）：

$L=1$ 一整行都是 $0$：一堆石子本身已经是“合并完成”的状态。$L=2$ 只有一种合并方式，$f(i,i+1)=a_i+a_{i+1}$（$i$ 是 0 基下标，$a_0=1$）。以 $f(0,2)$（区间 $1,3,5$）为例展开转移：断点 $k=0$ 给出 $f(0,0)+f(1,2)=0+8=8$，断点 $k=1$ 给出 $f(0,1)+f(2,2)=4+0=4$，取较小的 $4$ 再加上区间和 $1+3+5=9$，得 $13$。最后 $f(0,3)$ 的三个候选是 $k=0{:}\,0+17=17$、$k=1{:}\,4+7=11$、$k=2{:}\,13+0=13$，最小值 $11$ 加全段和 $11$ 得 $22$，与样例输出一致。

正确性：上界——任取断点 $k$，先把左段按最优方式合成一堆（$f(l,k)$），再把右段合成一堆（$f(k+1,r)$），最后合并这两堆（代价恰为 $S(l,r)$，因为此时桌上只剩这两堆，它们的质量和就是全段质量之和），这是一条合法方案。下界——设最优方案的最后一次合并断点为 $k^{\ast}$，这次合并之前左右两段各自已在自己区间内合成一堆（相邻合并无法跨越一个尚未合并的断点），故前半段花费 $\geqslant f(l,k^{\ast})$、后半段 $\geqslant f(k^{\ast}+1,r)$，总代价 $\geqslant f(l,k^{\ast})+f(k^{\ast}+1,r)+S(l,r)$。两侧夹紧即得递推式。递推只引用更短的区间，按长度填表不会出现循环依赖。

代码

ps 是前缀和，区间和写成 ps[j+1] - ps[i]；f[i][j] 就是 $f(l,r)$，初始化全 $0$ 顺便把 $f(l,l)=0$ 这条边界写好；best 收集断点 $k$ 的最小「左右两段代价之和」，最后一行把它加上本次合并的代价 $S(l,r)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 石子合并：区间 DP，按区间长度从小到大递推。
#include <cstdio>
#include <vector>

typedef long long ll;

const ll MAXN = 1005;

ll n;
ll stone[MAXN];
ll ps[MAXN];  // ps[i] = 前 i 堆的质量和
ll f[MAXN][MAXN]; // f[i][j]：把区间 [i, j] 合并成一堆的最小代价

int main() {
    if (scanf("%lld", &n) != 1) return 0; // 空输入安全返回
    for (ll i = 0; i < n; i++) scanf("%lld", &stone[i]);
    ps[0] = 0;
    for (ll i = 0; i < n; i++) ps[i + 1] = ps[i] + stone[i];

    for (ll length = 2; length <= n; length++) {
        for (ll i = 0; i + length - 1 < n; i++) {
            ll j = i + length - 1;
            ll best = -1; // 只作内层取最小值的初始上界
            for (ll k = i; k < j; k++) {
                ll cost = f[i][k] + f[k + 1][j]; // 左段代价 + 右段代价
                if (best < 0 || cost < best) best = cost;
            }
            f[i][j] = best + ps[j + 1] - ps[i]; // 补上最后一次合并自身的代价
        }
    }
    printf("%lld\n", f[0][n - 1]); // n = 1 时就是 0：只有一堆
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 20:35
# update_at: 2026-10-01 20:49

import sys
from itertools import accumulate

INF = 1 << 60  # 只作内层取最小值的初始上界；真实代价不超过 n * 1000 * (n-1) ≈ 9e7


def min_merge_cost(stone: list[int]) -> int:
    """链上石子合并的最小总代价：区间 DP，O(n^3) 时间、O(n^2) 空间。

    f[i][j] = 把区间 [i, j] 合并成一堆的最小代价。最后一次合并必然把区间劈成
    左段 [i, k] 与右段 [k+1, j]，两段的代价 f[i][k] + f[k+1][j] 之外，
    这一次合并自身还要付 S(i, j) = ps[j+1] - ps[i]，也就是这段的质量和。
    """
    n = len(stone)
    ps = list(accumulate(stone, initial=0))  # ps[i] = 前 i 堆的质量和
    f = [[0] * n for _ in range(n)]          # 初始全 0，正好就是长度 1 的区间（不必合并）
    for length in range(2, n + 1):
        # f[i][j] 只依赖更短的区间，所以按长度从小到大递推即可保证用到的值已经算好。
        for i in range(n - length + 1):
            j = i + length - 1
            row = f[i]  # 内层是热路径，把行取到局部变量，省掉每次的 f[i] 下标查找
            best = INF
            for k in range(i, j):
                cost = row[k] + f[k + 1][j]  # 左段代价 + 右段代价，k 是最后一次合并的断点
                if cost < best:
                    best = cost
            row[j] = best + ps[j + 1] - ps[i]  # 补上最后一次合并自身的代价
    return f[0][n - 1]  # n = 1 时就是 f[0][0] = 0：只有一堆，不需要任何合并


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    stone = [next(data) for _ in range(n)]
    print(min_merge_cost(stone))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：状态数 $\frac{N(N+1)}{2}=O(N^2)$，每个状态枚举 $O(N)$ 个断点，合计 $O(N^3)$。精确计数为 $\binom{N+1}{3}$；$N=300$ 时是 $4\,499\,950$ 次内层转移，实测最慢用例 0.17 s（时限 1000 ms）。
• 空间复杂度：$O(N^2)$ 个状态加一个长度 $N+1$ 的前缀和数组，$N=300$ 时约 $300\times300$ 个整数；实测峰值内存约 17 MB（限制 128 MB）。

总结

本题的关键不是“用 DP”，而是换一个枚举对象：暴力的对象是操作序列，同一棵合并树会被写成许多种先后顺序，规模按 $(N-1)!$ 爆炸；正解的对象是最后一次合并的断点，一棵合并树只对应一个断点，规模塌缩成 $N-1$。再加上“合并出来的新堆永远覆盖一段连续区间”，子问题就只由两个端点决定，$O(N^2)$ 个区间足以描述全部局面，于是得到区间 DP。转移里的 $S(l,r)$ 就是最后一次合并自身的代价，用前缀和 $O(1)$ 取得；按区间长度从小到大递推则保证被依赖的更短区间已经算好。

图示解析

最后一次合并的劈分

下图展示区间 $[1,n]$ 的最后一次合并：它必然把整段劈成左右两个连续子区间，并额外付出整段质量之和 $S(1,n)$。

1
2
3
4
5
6
7
8
9区间 [1, 2, 3, 4]（对应 0 基的 [0, 3]）的最后一次合并必然劈成左右两个连续子区间：

        [1 . . . . . . . . . . . . n]        代价 += S(1,n)（全段质量之和）
                 /            \
        [1 .. 2]              [3 .. 4]
         递归 f(1,2)=4         递归 f(3,4)=7

样例 [1, 3, 5, 2]：最优断点在第 2 堆之后，S(1,4) = 11，
于是 4 + 7 + 11 = 22。

观察重点：转移式里的 $S(l,r)$ 不是凭空加的，它就是最后一次合并自身的代价；左右两段各自还要继续合并，于是分别递归到 $f(l,k)$ 与 $f(k+1,r)$。由于每段都是原序列上的连续区间，状态只需要两个端点就能描述清楚。

从暴力到正解的路线

下图是从枚举合并顺序到区间 DP 的主线，只保留模型、关键观察、算法与答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16输入 a[1..n]，每次合并相邻两堆
     |
     v
暴力：枚举每一步合并哪两堆     搜索树规模 (n-1)!，n=300 不可能跑完
     |
     |  同一棵合并树的多种先后顺序被重复枚举 —— 只要看合并树的形状
     v
关键观察：最后一次合并把 [l,r] 劈成 [l,k] 与 [k+1,r]，代价 S(l,r) 与 k 无关
     |
     v
区间 DP：f(l,r) = min_k ( f(l,k) + f(k+1,r) ) + S(l,r)
     |
     |  依赖的区间都更短  ->  按区间长度 L = 2..n 递推
     |  S(l,r) 用前缀和 O(1) 取得
     v
答案 f(0,n-1)        O(n^3) 时间、O(n^2) 空间

观察重点：暴力与正解的差别不在“枚举的范围”，而在“枚举的对象”——暴力枚举的是操作序列（有 $(n-1)!$ 个且大量重复），正解枚举的是最后一次合并的断点 $k$（只有 $n-1$ 个且互不重复）。再加上“子区间仍然只由端点决定”这条性质，局面空间就从指数级塌缩成 $O(n^2)$ 个区间。