石子合并（弱化版）

题意

给出一排石子，每次只能合并相邻的两堆，代价等于这两堆石子的质量之和。多次合并后要把所有石子变成一堆，求最小总代价。

题目的关键限制是“只能合并相邻两堆”。这意味着任意时刻形成的新石子堆，都对应原序列中的一个连续区间。

思路

最直接的想法是按照题意暴力模拟：每一步都枚举当前要合并的相邻两堆，递归搜索所有可能的合并顺序。

先看一个可以直接验证想法的朴素解：

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

int dfs(vector<int> stones) {
    if (stones.size() == 1) {
        return 0;
    }

    int best = INT_MAX;
    for (int i = 0; i + 1 < (int)stones.size(); ++i) {
        vector<int> next = stones;
        int merged = next[i] + next[i + 1];
        next[i] = merged;
        next.erase(next.begin() + i + 1);
        // 暴力枚举这一步选择哪一对相邻石子合并
        best = min(best, merged + dfs(next));
    }
    return best;
}

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

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

    cout << dfs(stones) << '\n';
    return 0;
}

这个暴力写法是可信的，因为它完整枚举了所有合法操作顺序，但复杂度是指数级，只能拿来做小数据验证。

真正的优化点在于换一种观察角度。对于任意区间 [l, r]，如果它最终被合并成一堆，那么最后一步一定是把某个 [l, k] 和 [k+1, r] 合并起来。也就是说，我们不必关心“前面每一步怎么合并”，只需要关心“最后一次在哪里断开”。

设 dp[l][r] 表示把区间 [l, r] 合并成一堆的最小代价，那么有转移：

dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(l, r))

其中 l <= k < r，sum(l, r) 表示区间总质量。为了在转移时快速求区间和，用前缀和数组维护即可。

这张表展示 dp[l][r] 在几个典型区间上的含义：

状态	表示什么
`dp[2][2]`	第 2 堆单独存在，不需要合并，代价是 `0`
`dp[2][3]`	把第 2 堆到第 3 堆合成一堆的最小代价
`dp[1][4]`	把整段石子全部合成一堆的最小代价，也就是最终答案

读这张表时，重点是把 dp[l][r] 理解成“一个连续区间的子问题”。一旦状态这样定义，最后一次合并就天然对应一个断点 k。于是三重循环按区间长度递推，就能覆盖所有可能的最优方案。

实现时，brute.cpp 枚举的是当前操作顺序；main.cpp 枚举的是最后一次合并的断点。这就是两份代码的本质差别。

DP 公式

设 $sum(l,r)$ 表示区间 $[l,r]$ 的石子总质量， $dp_{l,r}$ 表示把区间 $[l,r]$ 合并成一堆的最小代价。边界为：

dp_{i,i}=0

枚举最后一次合并的断点 $k$ ：

dp_{l,r}=\min_{l\leqslant k<r}\left(dp_{l,k}+dp_{k+1,r}+sum(l,r)\right)

最终答案为：

dp_{1,n}

公式解释：区间最后一次合并一定会把 [l,r] 分成左右两段。左右两段各自先合并到最优，再付出整段石子总质量作为最后一次合并代价，枚举断点取最小值。

代码

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

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

    int n;
    cin >> n;
    vector<int> a(n + 1), sum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    const int INF = 0x3f3f3f3f;
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

    // dp[l][r] 表示把区间 [l, r] 合并成一堆的最小代价
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = INF;
            int seg_sum = sum[r] - sum[l - 1];
            for (int k = l; k < r; ++k) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + seg_sum);
            }
        }
    }

    cout << dp[1][n] << '\n';
    return 0;
}

复杂度

区间 DP 需要枚举区间长度、左端点和断点，所以时间复杂度是 $O(n^3)$ ，空间复杂度是 $O(n^2)$ 。

总结

这题的核心不是“怎么模拟合并”，而是识别出“相邻合并”对应连续区间结构。把思路从枚举操作顺序改成枚举最后一次合并位置后，就能自然得到区间 DP。

一图流解析

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