题解 | 石子合并

// 引入万能头文件，包含所有常用的STL库（竞赛场景常用）
#include<bits/stdc++.h>
// 使用std命名空间，避免重复书写std::前缀
using namespace std;

// 定义常量：N为区间最大长度，MAX为代价的初始极大值（用于求最小值的初始化）
const int N=400,MAX=1e9+10;

// 全局变量声明
int n;                  // n：表示要合并的区间总数/元素个数
int dp[N][N];           // dp[i][j]：动态规划数组，存储合并区间[i, j]的最小代价
int m[N];               // m数组：存储每个子区间的基础数值（如石子合并问题中的石子数量）
int sum_m[N];           // sum_m数组：m数组的前缀和，用于快速计算区间[i, j]的数值总和

// 核心求解函数：通过动态规划计算合并所有区间的最小代价
void solve(){
    // 枚举区间长度，从2开始（长度为1的区间无需合并，代价为0）
    for(int len=2;len<=n;len++){
        // 枚举区间的起点i，确保终点j=i+len-1不超过n
        for(int i=1;i<=n-len+1;i++){
            // 计算区间的终点j
            int j=i+len-1;
            // 初始化dp[i][j]为极大值，后续通过状态转移更新最小值
            dp[i][j]=MAX;
            // 计算区间[i, j]的数值总和（利用前缀和快速求解）
            int value=sum_m[j]-sum_m[i-1];
            // 枚举区间分割点k，将[i,j]拆分为[i,k]和[k+1,j]两部分
            for(int k=i;k<=j-1;k++){
                // 状态转移方程：合并[i,j]的最小代价 = min(当前值, 合并[i,k]的代价 + 合并[k+1,j]的代价 + 本次合并的基础代价)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+value);
            }
        }
    }
    // 输出合并整个区间[1,n]的最小代价
    cout<<dp[1][n]<<endl;
}

// 主函数：程序入口，负责输入数据、初始化并调用求解函数
int main(){
    // 关闭cin与stdio的同步，加速输入（竞赛常用优化）
    ios::sync_with_stdio(false);
    // 解绑cin和cout，避免cout刷新导致cin变慢
    cin.tie(0);
    
    // 输入区间总数n
    cin>>n;
    // 输入每个子区间的基础数值，并计算前缀和
    for(int i=1;i<=n;i++){
        cin>>m[i];
        // 前缀和公式：sum_m[i] = 前i-1项和 + 第i项
        sum_m[i]=sum_m[i-1]+m[i];
    }
    
    // 调用求解函数计算并输出结果
    solve();

    return 0;
}