python/TangDou/AcWing/SectionDP/282.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;
const int INF = 0x3f3f3f3f;

int n;
int s[N];    // 前缀和
int f[N][N]; // 表示将i到j合并成一堆的方案的集合,属性：最小值
// 石子合并
int main() {
    cin >> n;
    // 一维前缀和,直接略过了a[i]数组，只用了一个s[i]数组保存前缀和
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];

    memset(f, 0x3f, sizeof f);                // 预求最小，先设最大
    for (int i = 1; i <= n; i++) f[i][i] = 0; // 第i堆与第i堆是不需要合并的，代价为0

    // 区间DP模板
    for (int len = 1; len <= n; len++)           // 枚举区间长度
        for (int i = 1; i + len - 1 <= n; i++) { // 枚举区间左端点,右端点计算获取，保证右端点不出界
            int j = i + len - 1;                 // 区间的右端点
            // 枚举中间点k
            for (int k = i; k < j; k++)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
        }
    cout << f[1][n] << endl;
    return 0;
}