AcWing 282. 石子合并

◎

本节目标

枚举最后一次合并的分界点，用区间 DP 最小化总代价。

题意与约束

每次只能合并相邻两堆，代价为两堆石子总数，求把所有石子合成一堆的最小代价。

第一反应与重复子问题

最后一次合并一定把一个区间切成左右两段；左右两段的最优合并代价会被反复使用。

状态定义与转移推导

dp[left][right] 是合并闭区间的最小代价，枚举最后分割点 mid，再加整段石子和。前缀和在 O(1) 得到该段总和。

正确性依据

任一最优方案的最后一步对应某个 mid，子段若不是各自最优即可替换而变优，故枚举所有 mid 完备。

样例执行过程

[1,3,5,2] 先完成短区间，再在完整区间比较三种最后切分，最小总代价为 22。

代码实现

C++

C++17

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

long long minMergeCost(const vector<int>& stones) {
    int n = static_cast<int>(stones.size());
    vector<long long> prefix(n + 1);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + stones[i];
    }
    vector<vector<long long>> dp(n, vector<long long>(n));
    for (int length = 2; length <= n; length++) {
        for (int left = 0; left + length <= n; left++) {
            int right = left + length - 1;
            dp[left][right] = LLONG_MAX / 4;
            for (int mid = left; mid < right; mid++) {
                dp[left][right] = min(
                    dp[left][right],
                    dp[left][mid] + dp[mid + 1][right] + prefix[right + 1] - prefix[left]
                );
            }
        }
    }
    if (n == 0) {
        return 0;
    }
    return dp[0][n - 1];
}

#ifndef ALGORITHM_TUTORIAL_NO_MAIN
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) {
        return 0;
    }
    vector<int> stones(n);
    for (int& stone : stones) {
        cin >> stone;
    }
    cout << minMergeCost(stones);
}
#endif

Python

Python 3

import sys


def min_merge_cost(stones):
    n = len(stones)
    prefix = [0]
    for stone in stones:
        prefix.append(prefix[-1] + stone)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            dp[left][right] = min(
                dp[left][mid] + dp[mid + 1][right] + prefix[right + 1] - prefix[left]
                for mid in range(left, right)
            )
    return 0 if n == 0 else dp[0][n - 1]


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if data:
        print(min_merge_cost(data[1:1 + data[0]]))


if __name__ == '__main__':
    main()

复杂度分析

区间、分割点各一层，时间 O(n³)，二维表空间 O(n²)。

边界与易错点

单堆代价为零；前缀和应使用 prefix[right + 1] - prefix[left]，避免闭区间少算右端。

模式迁移

当代价来自最后一次切分时继续枚举分割点；当收益取决于最后保留元素时可迁移到戳气球。回到区间动态规划。