题解：P1775 石子合并（弱化版）

#include <bits/stdc++.h>
using namespace std;
//dp[i][j]石子i~j全部合并的最小代价
int dp[310][310],sum[310];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(dp,0x3f,sizeof dp);//在求min之前一定要赋无穷大
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>sum[i];
		sum[i]+=sum[i-1];//前缀和
		dp[i][i]=0;//石子i在合并前没有代价
	}
	//第一层：区间长度
	for (int len=2;len<=n;len++){
		//第二层：左端点
		for (int l=1;l<=n-len+1;l++){
			//右端点=左端点+长度-1
			int r=l+len-1;
			//第三层：左右堆的界限
			//左堆：l~mid，右堆：mid+1~r
			for (int mid=l;mid<r;mid++){
				//每次都要更新最小值
				//dp[l][mid]左堆的最小代价
				//dp[mid+1][r]右堆的最小代价
				//sum[r]-sum[l-1]左右堆的质量和，即这次合并的代价
				dp[l][r]=min(dp[l][r],dp[l][mid]+dp[mid+1][r]+(sum[r]-sum[l-1]));
			}
		}
	}
	cout<<dp[1][n];//区间1~n的合并最小代价
	return 0;
}