排除错误思路

乍看一眼示例，可能会有这样的想法：每次找出和最小的两个相邻元素合并。这是贪心的思路，但其实是错误的。

看下面的示例：{ 3，3，2，4 }。

贪心法过程如下：第一次合并为{ 3，5，4 }，代价5；第二次合并为{ 8，4 }，代价8；第三次合并为{ 12 }，代价12；总代价为5 + 8 + 12 = 25。

正确的合并过程如下：第一次合并为{ 6，2，4 }，代价6；第二次合并为{ 6，6 }，代价6；第三次合并为{ 12 }，代价12；总代价为6 + 6 + 12 = 24。

此题正确的思路是动态规划，标题区间dp已经给出了明确的提示。

动态规划

我们使用分治的思想，一个大区间可以由两个小区间合并而成。令dp[l][r]表示将区间[l, r]的所有元素合并为1个元素的最小代价。那么有状态转移方程——

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

其中sum(l, r) 表示区间[l, r]的所有元素之和，也就是合并[l, r]两个子区间的代价。该值可以使用前缀和的思路来求解。

c++的AC代码如下，注意使用long long。

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

int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 0;
        return 0;
    }
    vector<int> a(n + 1);
    vector<int> sum(n + 1);
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    cin >> a[1];
    sum[1] = a[1];
    for (int i = 2; i <= n; ++i) {
        cin >> a[i];
        dp[i - 1][i] = a[i - 1] + a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 2; i < n; ++i) {
        for (int l = 1; l <= n - i; ++l) {
            int r = l + i;
            long long tmp = LLONG_MAX;
            for(int j = l; j < r; ++j) {
                tmp = min(tmp, dp[l][j] + dp[j + 1][r]);
            }
            dp[l][r] = tmp + sum[r] - sum[l - 1];
        }
    }
    cout << dp[1][n];
}
// 64 位输出请用 printf("%lld")