区间DP

#include <iostream>
#include <algorithm>
#include <climits>     // INT_MAX
using namespace std;

const int N = 105;
const int INF = 1e9;   // 一个很大的数，代表"无穷大"
int a[N];              // a[i] = 第i堆石子的重量
int pre[N];            // pre[i] = 前i堆的总重量（前缀和）
int dp[N][N];          // dp[i][j] = 合并区间[i,j]的最小代价

int main() {
    int n;
    cin >> n;              // 读入石子堆数

    // 读入每堆石子的重量，并计算前缀和
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];  // 前缀和：pre[i] = a[1]+a[2]+...+a[i]
    }

    // 求区间[i,j]的总重量的辅助函数（也可以直接用前缀和）
    // sum(i,j) = pre[j] - pre[i-1]

    // 区间DP：按区间长度从小到大计算
    // len = 区间长度，从2开始（长度1不需要合并）
    for (int len = 2; len <= n; len++) {
        // i = 区间左端点
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;    // j = 区间右端点
            dp[i][j] = INF;         // 初始化为无穷大

            // 枚举分割点k（在k和k+1之间切一刀）
            for (int k = i; k < j; k++) {
                // 左半边[i,k]的最小代价 + 右半边[k+1,j]的最小代价
                // + 合并这两半的代价（区间总重量）
                int cost = dp[i][k] + dp[k+1][j] + (pre[j] - pre[i-1]);
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    cout << "最小合并代价: " << dp[1][n] << endl;  // 输出答案
    return 0;
}