3060: 合并石子 区间DP

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量n和数组a、dp
int n, a[110], dp[110][110];
int main() {
    // 初始化dp数组，所有元素设为一个很大的数（1e9）
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            dp[i][j] = 1e9;
        }
    }
    // 输入整数n
    cin >> n;
    // 输入数组a的元素并计算前缀和
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1]; // 计算前缀和
        dp[i][i] = 0; // 单个元素的最小合并代价为0
    }
    // 动态规划计算区间的最小合并代价
    for (int i = n; i >= 1; i--) {
        for (int j = i + 1; j <= n; j++) {// 枚举区间的右端点
            for (int k = i; k < j; k++) {// 枚举区间的中点
                // 更新dp[i][j]为最小的合并代价
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + (a[j] - a[i - 1]));
            }
        }
    }
    // 输出从第1个到第n个元素的最小合并代价
    cout << dp[1][n] << endl;
    return 0;
}