[NOI1995] 石子合并

形式化题目

给定一个长度为 $n$ 的环形序列 $a_1, a_2, \dots, a_n$ （首尾相邻）。

一次操作：从环上选出相邻的两堆，把它们合并成一堆，得分等于这两堆石子数之和。

连续操作 $n-1$ 次后只剩一堆。求所有合法操作顺序中，总得分的最小值与最大值。

约束： $1 \leqslant n \leqslant 100$ ， $0 \leqslant a_i \leqslant 20$ 。

解法路线

朴素模拟把「每一步合并哪一对」当作决策，搜索树是 $2^{n}$ 量级，只能做 $n \leqslant 8$ 的规模；正确的切入点是只看最后一次合并，它把问题切成了两个独立的、规模更小的同类问题——这正是区间 DP 的形态。环形则通过复制数组变成 $2n$ 长度的链来处理。

层次	适用约束	做法	复杂度	相对前层的推进
暴力模拟	$n \leqslant 8$	递归枚举「合并环上哪一对相邻石子」，记忆化记录剩余环	$O(\text{状态数})$ ，指数级	基线，只用来验证小数据
正解：区间 DP	$n \leqslant 100$	复制成 $2n$ 链，按区间长度递增递推 `dp[l][r] = opt_k dp[l][k] + dp[k+1][r] + sum(l,r)`，再枚举长度为 $n$ 的起点	$O(n^3)$	用「最后一次合并的断点」取代逐步模拟，把指数搜索压成多项式

表后说明：暴力层不是对外的正式解，它存在的意义是让「枚举合并顺序」这个最直白的想法落地，从而能直接看到它为什么爆炸；正解只把决策点从「每一步」换成「最后一次」，其余不变。

暴力解法

思路

最直接的想法就是照着题意模拟：当前环上还剩 $m$ 堆，枚举把哪一对相邻的合并，递归下去，返回剩余环的最优值，再加上本步得分。

环没有固定起点，所以同一个环可能以不同旋转出现。暴力里用 canonical() 把状态旋转到「最小元素开头」再记忆化，避免重复计算。

因为每步的得分只依赖本步合并的两堆（它们的和），所以递归返回时可以简单地把 merged 累加给子问题结果。

代码

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 直接按题意在环上枚举"合并哪一对相邻石子"，递归 + 记忆化。

const int INF = 0x3f3f3f3f;

int n;
map<vector<int>, pair<int, int> > memo;

// 把 vector 旋转到以最小元素（第一个出现处）开头，使同一个环只有一种表示。
static vector<int> canonical(const vector<int> &v) {
    int m = (int) v.size();
    int pos = 0;
    for (int i = 1; i < m; i++) {
        if (v[i] < v[pos]) pos = i;
    }
    vector<int> r;
    for (int i = 0; i < m; i++) r.push_back(v[(pos + i) % m]);
    return r;
}

// 暴力递归：当前 cur 表示环上剩余的石子堆（按环上顺序）。
pair<int, int> dfs(const vector<int> &cur) {
    int m = (int) cur.size();
    if (m == 1) return make_pair(0, 0);

    vector<int> key = canonical(cur);
    map<vector<int>, pair<int, int> >::iterator it = memo.find(key);
    if (it != memo.end()) return it->second;

    int best_min = INF;
    int best_max = -INF;

    for (int i = 0; i < m; i++) {
        int j = (i + 1) % m;
        int merged = cur[i] + cur[j];

        // 合并掉 i 和 j 后，从 j 的下一个位置开始，把剩下的 m-2 个元素
        // 接在 merged 后面，保持环上的相对顺序。
        vector<int> nxt;
        nxt.push_back(merged);
        for (int step = 1; step <= m - 2; step++) {
            nxt.push_back(cur[(j + step) % m]);
        }

        pair<int, int> sub = dfs(nxt);
        best_min = min(best_min, sub.first + merged);
        best_max = max(best_max, sub.second + merged);
    }

    pair<int, int> ans = make_pair(best_min, best_max);
    memo[key] = ans;
    return ans;
}

int main() {
    cin >> n;
    vector<int> stones(n);
    for (int i = 0; i < n; i++) cin >> stones[i];

    memo.clear();
    pair<int, int> ans = dfs(stones);
    cout << ans.first << '\n';
    cout << ans.second << '\n';
    return 0;
}

复杂度

状态数是「环上元素的多重集排列」级别，实际增长远快于 $2^n$ ， $n = 8$ 时已经接近极限。因此它只能做很小的数据，适合作为对拍基准。

瓶颈

每个状态都要枚举「合并哪一对」，而合并顺序的总数是组合爆炸的。我们并不需要知道中间每一步长什么样——只要知道某个区间被合成一堆的总代价，就可以把它整体当作一次「大合并」的零件。

正解

关键观察

考虑区间 $[l, r]$ 的最后一次合并：它一定把 $[l, r]$ 拆成相邻的两段 $[l, k]$ 与 $[k+1, r]$ ，其中两段各自都已经先合成了一堆。

这次合并的得分是 $[l, r]$ 全部石子之和 $S(l, r)$ ，与 $k$ 怎么选无关。

于是 $[l, r]$ 的答案只依赖两个更短区间的答案，加上一个固定的 $S(l, r)$ 。这就是区间 DP 的转移。

思路

先解决链上的版本。设

dp_min[l][r]：把链上区间 $[l, r]$ 合成一堆的最小总代价；
dp_max[l][r]：对应的最大总代价。

转移枚举断点 $k$ （ $l \leqslant k < r$ ）：

dp_{\min}[l][r] = \min_{l \leqslant k < r}\left(dp_{\min}[l][k] + dp_{\min}[k+1][r]\right) + S(l,r)

dp_{\max}[l][r] = \max_{l \leqslant k < r}\left(dp_{\max}[l][k] + dp_{\max}[k+1][r]\right) + S(l,r)

初值 dp[l][l] = 0（一堆石子不需要合并，代价为 0）。由于转移只用到比 $[l, r]$ 短的区间，按区间长度从小到大递推即可保证子问题已算好。

破环成链：把数组复制一遍得到长度 $2n$ 的序列 $a_1, \dots, a_n, a_1, \dots, a_n$ 。环上任意一种「从第 $i$ 堆之后切开」的方案，在复制后的数组里都对应一个长度为 $n$ 的连续区间 $[i, i+n-1]$ 。所以答案就是

\min_{1 \leqslant i \leqslant n} dp_{\min}[i][i+n-1], \qquad \max_{1 \leqslant i \leqslant n} dp_{\max}[i][i+n-1]

一个小规模推演

以样例 4 5 9 4 为例。复制后数组是 4 5 9 4 | 4 5 9 4。长度 2 的区间（只有一种合并方式）最低代价如下表：

区间	石子	合并得分
[1,2]	4, 5	9
[2,3]	5, 9	14
[3,4]	9, 4	13
[4,5]	4, 4	8

再往上是长度 3、4 的区间，每个都枚举断点取最优。最终四个长度为 4 的起点给出：

起点 $i$	区间	最小代价	最大代价
1	[1,4]	44	54
2	[2,5]	44	54
3	[3,6]	43	52
4	[4,7]	43	54

取所有起点的最小者的最小值 $43$ 、最大者的最大值 $54$ ，正是样例答案。注意最小值和最大值没有出现在同一个起点上——这也是本题容易错的地方：两个答案必须分别扫描所有起点，不能只在一个起点上同时取 min 和 max。

代码

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#include <bits/stdc++.h>
using namespace std;

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

int n;
int a[MAXN];
int sumv[MAXN];
int dp_min[MAXN][MAXN];
int dp_max[MAXN][MAXN];

// 计算区间 [l, r] 的石子总数。
int range_sum(int l, int r) {
    return sumv[r] - sumv[l - 1];
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }

    for (int i = 1; i <= 2 * n; i++) {
        sumv[i] = sumv[i - 1] + a[i];
    }

    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= 2 * n; j++) {
            dp_min[i][j] = INF;
            dp_max[i][j] = -INF;
        }
        dp_min[i][i] = 0;
        dp_max[i][i] = 0;
    }

    // 区间 DP：先枚举长度，再枚举左端点。
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= 2 * n; l++) {
            int r = l + len - 1;
            int seg_sum = range_sum(l, r);
            for (int k = l; k < r; k++) {
                dp_min[l][r] = min(dp_min[l][r], dp_min[l][k] + dp_min[k + 1][r] + seg_sum);
                dp_max[l][r] = max(dp_max[l][r], dp_max[l][k] + dp_max[k + 1][r] + seg_sum);
            }
        }
    }

    int ans_min = INF;
    int ans_max = -INF;
    for (int l = 1; l <= n; l++) {
        int r = l + n - 1;
        ans_min = min(ans_min, dp_min[l][r]);
        ans_max = max(ans_max, dp_max[l][r]);
    }

    cout << ans_min << '\n';
    cout << ans_max << '\n';
    return 0;
}

复杂度

区间 DP 的区间数是 $O((2n)^2) = O(n^2)$ ，每个区间枚举一个断点 $k$ ，所以时间 $O(n^3)$ （常数上界按 $2n$ 计算），空间 $O(n^2)$ 。

在 $n = 100$ 时， $2n = 200$ ，三重循环约 $1.3 \times 10^6$ 次转移，远低于时限；实测 $n=100$ 的数据 CPU 时间约 $1.1$ ms。

总结

这题是「环形区间 DP」的模板：关键只有两步。

找对决策点：不看中间每一步合并谁，只看最后一步把区间劈在哪里——这一步把指数搜索变成多项式 DP。
破环成链：复制数组，把所有长度为 $n$ 的连续区间都当成一次「切环」，最后在它们之间取 min / max。

两个答案要分别维护两张表、分别扫描所有起点，因为取到最小值的切法和取到最大值的切法一般不重合。

图示解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录