区间dp模板 石子归并

设有N堆沙子排成一排，其编号为1,2,3,…,N(N<=100)。每堆沙子有一定的数量。现要将N堆沙子并成为一堆。归并的过程只能每次将相邻的两堆沙子堆成一堆，这样经过N-1次归并后成为一堆。找出一种合理的归并方法，使总的代价最小。归并的代价是归并后堆的数量。

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

int stones[205];
int sum[205];
int n;
int dp[205][205];

int main() 
{
#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> n;

    for (int i = 0; i < n; ++i) {
        scanf("%d", &stones[i]);
        sum[i + 1] = sum[i] + stones[i];
    }

    for (int len = 2; len <= n; ++len) {
        //枚举长度
        for(int i = 0; i < n; ++i) {
            //枚举区间起点
            int end = i + len - 1;
            if (end >= n) {
                break;
            }
            dp[i][end] = INT32_MAX;
            for (int j = i; j < end; ++j) {
                //枚举分割点
                dp[i][end] = min(dp[i][end], dp[i][j] + dp[j + 1][end] + sum[end + 1] - sum[i]);
            }
        }
    }

    cout << dp[0][n-1];

    fclose(stdin);
    fclose(stdout);
    return 0;
}