「一本通 5.1 例 1」石子合并

形式化题目

有 $n$ 堆石子 $a_1, a_2, \dots, a_n$ 排成一个环（ $a_n$ 与 $a_1$ 相邻）。每次操作选择相邻的两堆，把它们合并成一堆，得分为合并后这一堆的石子数。操作共进行 $n-1$ 次，最终只剩一堆。在全部合法的操作顺序中，求得分总和的最小值与最大值。

正解

思路

先看最朴素的思路：每一步枚举所有相邻的有序对合并，递归 $n-1$ 层。第 $1$ 步有 $n$ 种选择、第 $2$ 步有 $n-1$ 种……方案数约为 $n!$ ， $n=200$ 时完全不可行。要消除的瓶颈就是"枚举整个操作序列"。

关键观察：把视角从"每一步"换到"某一段"。 任意一个合法的合并方案，都等价于不断把相邻的若干堆并成一段，最后整段并成一堆。也就是说，方案可以组织成"把区间 $[i, j]$ 合并成一堆"这个子问题。

再往下一步：假设区间 $[i, j]$ 最终合并成一堆，那么最后一次合并一定把 $[i, j]$ 切成左右两个真子区间 $[i, k]$ 和 $[k+1, j]$ （ $i \leqslant k < j$ ）。而这次合并的得分固定是整段之和

\text{sum}(i, j) = a_i + a_{i+1} + \dots + a_j

——它只和区间边界有关，和断点 $k$ 怎么选无关。于是最优化只作用在左右两段上：

f[i][j] = \min_{i \leqslant k < j}\big(f[i][k] + f[k+1][j]\big) + \text{sum}(i, j)

$g[i][j]$ 把 $\min$ 换成 $\max$ 同理。边界是 $f[i][i] = g[i][i] = 0$ ：一堆石子不需要合并，得分为 $0$ 。

以样例 4 5 9 4 为例， $n=4$ 时各长度区间的 $f$ 值（下标从 0 开始）如下表：

区间长度	$[0,3]$	$[1,4]$	$[2,5]$	$[3,6]$	$[4,7]$
$1$	$0$	$0$	$0$	$0$	$0$
$2$	$9$	$14$	$13$	$8$	$9$
$3$	$27$	$31$	$25$	$21$	$27$
$4$	$44$	$44$	$43$	$43$	$44$

注意长度 $1$ 的格子全都是 $0$ ，长度 $4$ 时同一段石子因起点不同出现了 $43$ 与 $44$ 两种答案——这正是"环"带来的差异。

环怎么处理？ 上面推的是链。环形方案的特点是：只要最终合并顺序不跨越某条边，它就和一条链上的方案一一对应。做法是把序列复制一份接到末尾，得到长度 $2n$ 的序列 $a_1, \dots, a_n, a_1, \dots, a_n$ ；那么每一个长度恰好为 $n$ 的窗口 $[r, r+n-1]$ （ $0 \leqslant r < n$ ）就代表"从第 $r$ 堆开始、在第 $r-1$ 堆处断开"的那种环形方案。枚举所有 $r$ ，对 $f[r][r+n-1]$ 取最小、对 $g[r][r+n-1]$ 取最大即可。

递推方向由区间长度决定：长度 $L$ 只依赖长度更小的子区间，所以外层按 $L$ 从小到大、内层枚举起点 $i$ 与断点 $k$ 。区间和用前缀和 $O(1)$ 取出： $\text{sum}(i, j) = \text{pre}[j+1] - \text{pre}[i]$ 。

取最小值时需要哨兵：用 $\text{sum}(\text{全部}) \times n + 1$ 作为"正无穷"，因为任何方案的得分都不会超过 $n$ 倍的石子总数（每次得分不超过总和，共 $n-1$ 次）。

代码

Python 版：

python

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#!/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-09-30 19:25
# update_at: 2026-09-30 19:25

import sys

INF = 10 ** 9  # 最小值表的哨兵：比任何合法得分（总和 <= 200*10^9）都小的上界由 BIG 保证


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    stone = [next(data) for _ in range(n)]
    BIG = sum(stone) * n + 1  # 任何方案得分都 <= n * 总和，用它当正无穷

    # 环形 → 链形：把序列接一份在后面，长度为 m 的区间就覆盖了任意环形起点的 m 堆
    a = stone * 2
    m = 2 * n  # 实际只用前 m 个下标；区间 [i, j] 表示第 i..j 堆合并成一堆

    # pre[k] = 前 k 堆的和，区间得分用 pre[j+1]-pre[i] 一次减出来
    pre = [0] * (m + 1)
    for k in range(m):
        pre[k + 1] = pre[k] + a[k]

    # f[i][j] / g[i][j]：把 [i, j] 合并成一堆的最小 / 最大得分
    f = [[0] * m for _ in range(m)]
    g = [[0] * m for _ in range(m)]

    for length in range(2, n + 1):  # 合并 length 堆；length=1 的区间本身不用花钱
        for i in range(m - length + 1):
            j = i + length - 1
            total = pre[j + 1] - pre[i]  # 最后一次合并必得的分：两段之和就是整段和
            best_min, best_max = BIG, -1
            for k in range(i, j):  # 枚举断点：左段 [i,k] 与右段 [k+1,j] 先各自成堆
                left_min, left_max = f[i][k], g[i][k]
                right_min, right_max = f[k + 1][j], g[k + 1][j]
                s_min = left_min + right_min
                s_max = left_max + right_max
                if s_min < best_min:
                    best_min = s_min
                if s_max > best_max:
                    best_max = s_max
            f[i][j] = best_min + total
            g[i][j] = best_max + total

    # 拆环的每个位置 r 都是候选起点，起点固定的链长 n 区间 [r, r+n-1] 就是该方案
    print(min(f[r][r + n - 1] for r in range(n)))
    print(max(g[r][r + n - 1] for r in range(n)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/**
 * 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-04 22:20
 * update_at: 2026-10-04 22:20
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 405; // 2n + 5，环拆成链后长度翻倍

typedef long long ll;

ll n, m;      // n 堆石子；m = 2n 为拆环成链后的总长
ll a[MAXN];   // 拆环后的石子序列：原序列接一份在后面
ll pre[MAXN]; // pre[k] = 前 k 堆石子之和，O(1) 取区间和
ll f[MAXN][MAXN]; // f[i][j]：把区间 [i,j] 合并成一堆的最小得分
ll g[MAXN][MAXN]; // g[i][j]：把区间 [i,j] 合并成一堆的最大得分
ll BIG;       // 最小值表的哨兵，任何合法得分都达不到

// 读入并把环拆成两倍长的链。
void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (ll i = 1; i <= n; i++) {
        a[i + n] = a[i]; // 复制一份接到末尾，破环成链
    }
    m = 2 * n;
}

void solve() {
    // 前缀和：sum(i,j) = pre[j] - pre[i-1]
    pre[0] = 0;
    for (ll i = 1; i <= m; i++) {
        pre[i] = pre[i - 1] + a[i];
    }

    // 哨兵：任何方案得分不超过 n 倍石子总和（每次得分 <= 总和，共 n-1 次）
    BIG = pre[n] * n + 1;

    // 长度 1 的区间 f = g = 0（全局数组默认即 0）
    // 按区间长度从小到大递推：长度 L 只依赖更短的子区间
    for (ll len = 2; len <= n; len++) {
        for (ll i = 1; i + len - 1 <= m; i++) {
            ll j = i + len - 1;
            ll sum_ij = pre[j] - pre[i - 1]; // 最后一次合并必得整段和，与断点无关
            ll best_min = BIG;
            ll best_max = -1;
            // 枚举断点：左段 [i,k]、右段 [k+1,j] 先各自合成一堆
            for (ll k = i; k < j; k++) {
                ll s_min = f[i][k] + f[k + 1][j];
                ll s_max = g[i][k] + g[k + 1][j];
                if (s_min < best_min) best_min = s_min;
                if (s_max > best_max) best_max = s_max;
            }
            f[i][j] = best_min + sum_ij;
            g[i][j] = best_max + sum_ij;
        }
    }

    // 每个长度为 n 的窗口 [r, r+n-1] 对应一种断环方式，枚举所有起点取最值
    ll ans_min = BIG;
    ll ans_max = -1;
    for (ll r = 1; r <= n; r++) {
        if (f[r][r + n - 1] < ans_min) ans_min = f[r][r + n - 1];
        if (g[r][r + n - 1] > ans_max) ans_max = g[r][r + n - 1];
    }

    cout << ans_min << "\n";
    cout << ans_max << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(n^3)$ 。状态数 $O(n^2)$ （在 $2n$ 上有 $O((2n)^2)$ 个区间），每个状态枚举 $O(n)$ 个断点， $n \leqslant 200$ 时约为 $8 \times 10^6$ 次转移。
空间复杂度： $O(n^2)$ ，即两张 $(2n) \times (2n)$ 的 DP 表。

总结

把"枚举操作序列"改写成"枚举区间"是本题的核心一步：最后一次合并的得分只由区间和决定，与断点无关，最优化因此可以下推到子区间。
环形问题用"复制一份接到末尾 + 枚举长度 $n$ 的窗口"转成 $O(n)$ 条链，是环形 DP 的通用技巧。
与之同名但要求环形、且合并后仍相邻的最优三角剖分类问题（如"环形石子合并 + 凸多边形三角剖分"），也用同一套"复制成链 + 区间 DP"框架。

「一本通 5.1 例 1」石子合并

目录

形式化题目

正解

思路

代码

复杂度

总结