形式化题目

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

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

把合并过程画成一棵二叉树：叶子从左到右是 $a_1..a_N$，每个内部结点代表一次合并、其覆盖的是一段连续区间。每次合并的代价就是该内部结点所覆盖区间的元素之和，于是

题目即：在保持叶子顺序的前提下选一棵二叉树，使内部结点的区间和之和最小。

样例 $a=(1,3,5,2)$：先合并 $(1,3)\to4$、再合并 $(5,2)\to7$、最后合并 $4+7=11$，总代价 $4+7+11=22$。

暴力解法

思路

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

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

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

代码

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

复杂度

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

每次模拟还要 $O(N)$ 维护局面，总时间 $O(N!)$ 量级，空间 $O(N)$ 递归栈。

瓶颈

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

但表里也有一个决定性的观察：真正决定总代价的是每次合并在哪里断开，也就是那棵合并树的形状，而不是"左右两段谁先合"。把枚举对象从操作序列换成断点，规模立刻从 $(N-1)!$ 塌缩成可枚举的量；只是接下来还要把「每个区间的每一条可能的断点」也砍掉，才够 $N=5000$ 用。

正解

思路

第一步：换成枚举断点。 把 $a_i..a_j$ 合并成一堆，最后一步必然是：某个断点 $k$ 让左边 $a_i..a_k$ 已经合成一堆、右边 $a_{k+1}..a_j$ 已经合成一堆，再把这两堆合并。这一步的代价是这一段的和 $S(i,j)=\sum_{t=i}^{j}a_t$，与 $k$ 无关；左右两边各自怎么合成那一堆互不影响。于是

$f(i,j)$ 依赖的两个区间都严格比 $[i,j]$ 短，所以按区间长度 $L=j-i+1$ 从小到大递推即可，$S(i,j)$ 用前缀和 $S(i,j)=ps_{j+1}-ps_i$ 一次取得。这是本题的前置题目 3145 的做法，状态数 $O(N^2)$，但每个状态要枚举 $O(N)$ 个 $k$，合计 $O(N^3)$——$N=5000$ 约需 $2\times10^{10}$ 次转移，必须继续优化。

第二步：断点范围可以砍掉一大截。 记 $p(i,j)$ 为 $f(i,j)$ 取到最小值的那个断点。关键性质是：$w(i,j)=S(i,j)$ 满足四边形不等式

代入区间和定义就能看清：把 $[a,c]$ 与 $[b,d]$ 合起来，正好覆盖 $[a,d]$，只是把中间段 $[b,c]$ 数了两遍，所以 $w(a,c)+w(b,d)=S(a,d)+S(b,c)$；而右边 $w(a,d)+w(b,c)$ 本就是 $S(a,d)+S(b,c)$。两边恒等，等号总成立，四边形不等式自然满足；又因为质量都是正的，$w$ 随区间增大而不减。在转移代价满足四边形不等式且单调时，区间 DP 的最优断点随区间单调：

这正是本题标签里的"四边形不等式优化"（也叫 Knuth 优化）。两个端点都是上一层已算好的值：下界来自长度 $L-1$ 的区间 $[i,j-1]$，上界来自长度 $L-1$ 的区间 $[i+1,j]$。于是 $f(i,j)$ 只需在 $[p(i,j-1),\,p(i+1,j)]$ 里试断点。

第三步：算清转移总数只有 $O(N^2)$。 固定长度 $L$，左端点 $i=0..m-1$（$m=N-L+1$），总转移次数

对 $i$ 求和时中间项两两相消，只剩首尾：$p(m,m+L-1)-p(0,L-1)+m\leqslant N+m\leqslant 2N$。再对 $L=2..N$ 求和得 $O(N^2)$——比 $O(N^3)$ 少了一个 $N$ 的因子。实测 $N=5000$ 时一共 $24\,978\,596$ 次转移，约 $N^2$。

样例 $a=(1,3,5,2)$ 的完整递推过程（下标 0 基，$f$ 只列上三角；"候选"里是 $(k,\,f(i,k)+f(k+1,j))$）：

看最后一行：如果不优化，$[0,3]$ 要试 $k=0,1,2$ 三个断点（候选 $17,11,13$）；现在由 $p(0,2)=1$ 与 $p(1,3)=1$ 夹出范围 $[1,1]$，只剩 $k=1$ 一个候选，直接得到最优值 $11$。这就是优化的全部收益：不是少算某个状态，而是每个状态少试断点。

第四步：为什么这样就能一次批量算完。 固定长度 $L$ 时，各区间是 $[i,i+L-1]$，断点范围依次是

1
2
3
4
5
6
7
8
9
10
11区间 i=0  : [p(0,L-1)   , p(1,L)    ]
区间 i=1  : [p(1,L)     , p(2,L+1)  ]
区间 i=2  : [p(2,L+1)   , p(3,L+2)  ]
   ...
区间 i=m-1: [p(m-1,L+m-2), p(m,L+m-1)]     m = N-L+1

相邻两个区间共享一个端点：前一个的上界 = 后一个的下界。
把这些范围首尾相接拼成一条长数组：

| 区间 0 的候选 | 区间 1 的候选 | 区间 2 的候选 | ... |
0              c1             c2                  total   <- segs：每段起点

它们首尾相接、互不重叠，“每个区间取最小"就等价于"把这条长数组按段切开、每段取最小”——这正是 np.minimum.reduceat 一次能干完的事。Python 的逐格循环做不到 $2.5\times10^7$ 次转移（实测 4.4 s），但把这些转移整理成一条数组交给 numpy，就只有 $O(N)$ 轮、每轮 $O(N)$ 长度的批量运算了。

把 $f$ 压成一维上三角表（f[base[i] + (j-i)]）后，一层循环就是下面五件事，全部是整数组运算：

决策点则用「先找出所有等于本段最小值的候选，再取每段第一个」得到。这样取到的是最小的最优断点，由 $p(i,j)\leqslant p(i+1,j)$ 可知它仍然满足决策单调，下一层直接用。

正确性：上界——任取断点 $k$，先把左右两段各自按最优方式合成一堆（$f(i,k)$、$f(k+1,j)$），再合并这两堆（代价恰为 $S(i,j)$，因为此时桌上只剩这两堆），这是一条合法方案。下界——设最优方案的最后一次合并断点为 $k^\ast$，这次合并之前左右两段已各自在区间内合成一堆（相邻合并无法跨越尚未合并的断点），故花费 $\geqslant f(i,k^\ast)+f(k^\ast+1,j)+S(i,j)$。两侧夹紧即得递推式。递推只引用更短的区间，按长度填表不会循环依赖。决策范围的正确性由四边形不等式给出 $p(i,j)\in[p(i,j-1),p(i+1,j)]$，而这两个端点都是上一层已经算出的最小最优断点，范围一定非空（$p(i,j-1)\leqslant p(i+1,j)$）。

代码

f 是一维压平的上三角表，多留的第 $n$ 行是"空区间"哨兵行（恒 0），专门服务 $k=j$ 时的 $f(j+1,j)=0$，这样取右半段代价时永不越界。dec 在每层循环结束时被覆盖成本层的决策点，正好充当下一层的 lo/hi。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * 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 13:00
 * update_at: 2026-10-10 13:00
 */

// 石子合并：区间 DP + 四边形不等式（Knuth 优化），O(n^2)
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

int n;

// 上三角表逐个区间存：第 i 行放 f[i][i..n-1]，f[i][j] 落在 off(i) + (j - i)
int off(int i) {
    return i * n - i * (i - 1) / 2;
}
// f[i][j]：把区间 [i,j] 合并成一堆的最小代价（用 int 存，与原实现一致）
vector<int> f;
// opt[i][j]：区间 [i,j] 的最优断点
vector<unsigned short> opt;
vector<ll> ps; // ps[i] = 前 i 堆的质量和

int main() {
    if (scanf("%d", &n) != 1) {
        return 0;
    }
    ps.assign(n + 1, 0);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        ps[i + 1] = ps[i] + x;
    }
    f.assign(n * n, 0);
    opt.assign(n * n, 0);
    for (int i = 0; i < n; i++) {
        opt[off(i)] = (unsigned short)i;
    }

    for (int length = 2; length <= n; length++) {
        for (int i = 0; i + length - 1 < n; i++) {
            int j = i + length - 1;
            // 最优断点随区间单调：p[i][j-1] <= p[i][j] <= p[i+1][j]
            int lo = opt[off(i) + (j - 1 - i)];
            int hi = opt[off(i + 1) + (j - i - 1)];
            ll best = -1;
            int bk = lo;
            for (int k = lo; k <= hi; k++) {
                ll v = (ll)f[off(i) + (k - i)] + f[off(k + 1) + (j - k - 1)];
                if (best < 0 || v < best) {
                    best = v;
                    bk = k;
                }
            }
            f[off(i) + (j - i)] = (int)(best + (ps[j + 1] - ps[i]));
            opt[off(i) + (j - i)] = (unsigned short)bk;
        }
    }
    printf("%d\n", f[off(0) + (n - 1)]);
    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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69#!/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 23:11
# update_at: 2026-10-01 23:20

# N 到 5000，O(N^3) 区间 DP 要 2.1e10 次转移，逐格写的 Python 循环撑不住；
# 即便用四边形不等式把转移压到约 2.5e7 次，逐格 Python 也还要 4 秒多。
# 四边形不等式把每个区间的断点收窄到 [p[i][j-1], p[i+1][j]]，而同一长度下各区间
# 待枚举的断点首尾相接、互不重叠，于是“逐区间取最小值”就是一次 minimum.reduceat，
# 整道题按区间长度递推 O(N) 轮，每轮全是 numpy 批量操作。

import sys

import numpy as np

IDX = np.int32  # 决策点与上三角表的下标 < 1.3e7，int32 足够；索引数组内存减半


def min_merge_cost(stone: np.ndarray) -> int:
    """链上石子合并的最小总代价：区间 DP + 四边形不等式优化，O(n^2) 时间与空间。

    f[i][j] 是把区间 [i, j] 合并成一堆的最小代价。最后一次合并必然把区间劈成
    [i, k] 与 [k+1, j]，这次合并自身要付 S(i, j)（= ps[j+1] - ps[i]，与 k 无关），
    于是 f[i][j] = min_{i<=k<j} (f[i][k] + f[k+1][j]) + S(i, j)。

    合并代价 S 满足四边形不等式，最优断点 p[i][j] 随区间单调，即
    p[i][j-1] <= p[i][j] <= p[i+1][j]；两个端点都是更短区间在上层算好的值，
    故枚举范围收缩为 [p[i][j-1], p[i+1][j]]，全部区间的转移次数合计 O(n^2)。
    """
    n = stone.size
    ps = np.zeros(n + 1, dtype=np.int64)
    np.cumsum(stone, out=ps[1:])                    # ps[i] = 前 i 堆的质量和
    start = np.arange(n + 1, dtype=np.int64)        # 上三角逐个区间存：第 i 行放 f[i][i..n-1]
    base = (start * n - start * (start - 1) // 2).astype(IDX)  # 第 i 行的起始偏移
    f = np.zeros((n + 1) * (n + 1) // 2, dtype=np.int32)       # f[i][j] 落在 base[i] + (j - i)
    # 第 n 行是“空区间”哨兵行：f[k+1][j] 在 k = j 时落到它，值恒为 0，正好就是空区间的代价。
    dec = np.arange(n, dtype=IDX)                   # 上一层（长度 1 的区间）的最优断点

    for length in range(2, n + 1):
        m = n - length + 1                          # 这个长度下区间个数，左端点 i = 0..m-1
        lo, hi = dec[:m], dec[1:m + 1]              # p[i][j-1] 与 p[i+1][j]，断点下界与上界
        counts = hi - lo + 1                        # 每个区间要试的断点个数
        segs = np.cumsum(counts, dtype=IDX) - counts
        rows = np.repeat(np.arange(m, dtype=IDX), counts)       # 候选断点所属的区间左端 i
        ks = np.arange(int(counts.sum()), dtype=IDX)            # 全部候选断点拼成一条长链
        ks -= np.repeat(segs, counts)                           # 减去所在区间的起点
        ks += np.repeat(lo, counts)                             # 就是区间内的断点 k
        end = rows + (length - 1)                   # 区间右端 j；S(rows, end) = ps[end+1] - ps[rows]
        # 候选值 f[i][k] + f[k+1][j]：两下标都落在 i <= j 的上三角里，越界时落到第 n 行的空区间哨兵 0。
        # 每个 f 是“被合并元素 × 某段和”，总和不超过 b·n²，b <= 1000 时 < 4.7e8，int32 装得下。
        cost = f[base[rows] + (ks - rows)] + f[base[ks + 1] + (end - ks - 1)]
        best = np.minimum.reduceat(cost, segs)      # 每个区间的最小“左右两段代价之和”
        hit = np.flatnonzero(cost == np.repeat(best, counts))   # 该区间内达到最小值的候选
        dec = ks[hit[np.searchsorted(hit, segs)]]   # 取第一个（最小的）最优断点，作为区间决策
        f[base[:m] + (length - 1)] = best + (ps[length:length + m] - ps[:m])  # 补上最后一次合并

    return int(f[n - 1])  # n = 1 时就是 f[0] = 0：只有一堆，不需要任何合并


def solve() -> None:
    data = np.fromstring(sys.stdin.buffer.read(), dtype=np.int64, sep=" ")
    n = int(data[0])
    print(min_merge_cost(data[1:1 + n]))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：转移总数 $O(N^2)$（精确约 $N^2$；$N=5000$ 时实测 $24\,978\,596$ 次）。Python 侧外层 $O(N)$ 轮，每轮是长度 $O(N)$ 的 numpy 批量操作，循环开销也是 $O(N)$。
• 空间复杂度：$O(N^2)$，f 用 int32 压成一维上三角，$N=5000$ 时约 12.5 MB；每轮临时数组不超过 $2N$ 个元素。
• 实测：本机 data/p6（$N=5000$）约 0.7 s、峰值内存约 79 MB；其余 5 组测例都在 0.09 s 以内。本题限时 1000 ms、内存 128 MB：Python 在评测机上仍有 TLE 风险（纯 Python 逐格写同样算法要 4.4 s，这里靠把转移全部向量化才压到 0.7 s 量级）；同样的算法在 C++ 里就是 rainboy.cpp 那 20 行三层循环（断点范围此时只有 $O(N)$ 个），本机实测约 0.15 s，是稳妥的正解形态。

总结

本题的关键不是"用 DP"，而是两次换对象：

1. 把操作序列换成断点（3145 已完成）：同一棵合并树会被写成许多种先后顺序，枚举操作序列是 $(N-1)!$，枚举"最后一次合并在哪里断开"只有 $N-1$ 种，于是子问题只由两个端点决定，得到 $O(N^2)$ 个状态的区间 DP。
2. 把"每条断点"换成"有效的断点范围"：合并代价 $S(i,j)$ 满足四边形不等式，最优断点随区间单调，$p(i,j-1)\leqslant p(i,j)\leqslant p(i+1,j)$，而这两个端点都是上一层的结果。对固定长度求和时中间项两两相消，转移总数从 $O(N^3)$ 降到 $O(N^2)$。

优化"少试断点"这一点，还顺带把 $O(N^2)$ 次转移变成了 $O(N)$ 轮"首尾相接、互不重叠的批量取最小"，于是 Python 也能在 $N=5000$ 上跑完：算法层的 $O(N^2)$ 与实现层的 numpy 分段归约是两件事，前者保证复杂度，后者保证常数。

图示解析

从暴力到正解的路线

下图是本题只保留模型、关键观察与算法的路线图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20输入 a[1..N]，每次合并相邻两堆
     |
     v
暴力：枚举每一步合并哪两堆            方案数 (N-1)!，N=5000 无法枚举
     |
     |  同一棵合并树的多种先后顺序被重复枚举 —— 只看合并树的形状
     v
区间 DP：f(i,j) = min_k ( f(i,k) + f(k+1,j) ) + S(i,j)          O(N^3) 转移
     |
     |  关键观察：w(i,j)=S(i,j) 满足四边形不等式 -> 最优断点单调
     |  p(i,j-1) <= p(i,j) <= p(i+1,j)，两端都是上一层算好的值
     v
Knuth 优化：每个区间只试 [p(i,j-1), p(i+1,j)] 内的断点          O(N^2) 转移
     |
     |  同一长度下，各区间的断点范围首尾相接、互不重叠
     v
向量化：把整层候选拼成一条长数组，minimum.reduceat 分段取最小
     |
     v
答案 f(0, N-1)

观察重点：从暴力到区间 DP 换的是枚举对象（操作序列 → 断点），规模从阶乘塌缩成 $N-1$；从区间 DP 到 Knuth 优化换的是枚举范围（每条断点 → 单调夹出的区间），规模从 $O(N^3)$ 降到 $O(N^2)$。两步都不是"少算状态"，而是"少试候选"，所以每次都能用同一个递推式承接，不必重写模型。

断点范围是怎么夹出来的

下图用样例里最长的区间 $[0,3]$ 说明断点收缩到什么程度。

1
2
3
4
5
6
7
8
9
10
11
12样例 a = [1, 3, 5, 2]，区间 [0,3]：

  朴素区间 DP：k = 0, 1, 2 全部要试
      k=0: f(0,0) + f(1,3) = 0 + 17 = 17
      k=1: f(0,1) + f(2,3) = 4 +  7 = 11      <- 最小
      k=2: f(0,2) + f(3,3) = 13 + 0 = 13

  Knuth 优化：下界 = p(0,2) = 1（区间 [0,2] 的最优断点）
              上界 = p(1,3) = 1（区间 [1,3] 的最优断点）
              范围 [1,1] 只剩 k = 1 一个候选，直接得 11

  f(0,3) = 11 + S(0,3) = 11 + 11 = 22        <- 样例输出

观察重点：范围的两个端点分别来自左邻区间 $[i,j-1]$ 和右邻区间 $[i+1,j]$，两者都比 $[i,j]$ 短一层，所以按长度递推时它们已经算好，不需要额外预计算。当两个端点重合时范围收缩成一个点，这一层的转移就完全免费了——$N=5000$ 时总转移数只有约 $N^2$ 就是这个原因。