数位DP 石子合并 模板题

题目

有n堆石子排成一排，每堆石子有一定的数量，将n堆石子合并成一堆。合并的规则是每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数，求最小花费。

题解代码

#include<bits/stdc++.h>
using namespace std;

int sum[1010];
int dp[1010][1010], s[1010][1010];
int n, x;

int main(void)
{
    while (~scanf("%d", &n)) {
        sum[0] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            sum[i] = sum[i - 1] + x;
        }
        for (int i = 1; i <= n; i++) {
            dp[i][i] = 0;
            s[i][i] = i;
        }
        for (int len = 1; len < n; len++) {
            for (int i = 1; i <= n - len; i++) {
                int j = i + len;
                dp[i][j] = INF;
                for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++) {
                    if (dp[i][k] + dp[k + 1][j] + sum[j] - sum[i -1] < dp[i][j]) {
                        dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
                        s[i][j] = k;
                    }
                }
            }
        }
        cout << dp[1][n] << endl;
    }

    return 0;
}