解题思路

由于每次只能合并相邻的两堆石子，因此事实上，我们每次合并总是合并连续的两段。设f(l, r)表示使得l - r号石子堆合并为一堆的最小代价，我们可以枚举分界点k，即看作是将l - k和(k + 1) - r号两堆石子合并，且其代价是l到r号石子堆的重量之和（此处用前缀和优化），因此状态转移方程为f(l, r) = max[l <= k < r](f(l, k) + f(k + 1, r)) + ∑[l <= i <= r](wi)。
 

C++代码

#include <iostream>
#include <array>
#include <algorithm>

#define MAXN 512
#define INF 0x7fffffff

std::array<int, MAXN> sum;
std::array<std::array<int, MAXN>, MAXN> f;

int main() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> sum[i];
        sum[i] += sum[i - 1];
    }
    
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            f[l][r] = INF; 
            for (int k = l; k < r; k++) {
                f[l][r] = std::min(f[l][r], f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);
            }
        }
    }
...