区间 DP（石子合并）

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 847 字

枚举区间长度与分裂点合并两子区间

动态规划
区间DP

前置内容

01 背包

正文

// 区间 DP：石子合并
// 枚举区间长度与左端点
// 中间切分，合并两子区间
// 求最小总代价
#include <cstdio>
int a[305], s[305], f[305][305];
int n, ans = 1e9;
int main() {
    scanf("%d", &n);
    // 前缀和便于算区间和
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    // 长度从 2 起（单堆无需合）
    for (int len = 2; len <= n; len++) {
        // 右端点最大下标
        int end = n - len + 1;
        for (int i = 1; i <= end; i++) {
            int j = i + len - 1;
            // 初值设很大
            f[i][j] = 1e9;
            // 枚举分裂点
            for (int k = i; k < j; k++) {
                // 左 + 右 + 整段和
                int v = f[i][k]
                    + f[k + 1][j]
                    + s[j] - s[i - 1];
                if (v < f[i][j])
                    f[i][j] = v;
            }
        }
    }
    printf("%d", f[1][n]);
    return 0;
}

区间 DP（石子合并）

前置内容

正文

CSP-J · 编程模板的其它内容