#include<iostream>
#include<cstring>
using namespace std;
int a[301],dp[301][301];			//dp[i][j]存储从i合并到j的最小代价 
int qzh[301];			//前缀和数组 

int main()
{
	memset(dp,0x3f,sizeof dp);		//初始化为0x3f防止溢出 
	int n;
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		dp[i][i]=0;					//自己与自己合并代价为0 
		qzh[i]=qzh[i-1]+a[i];		
	}
	
	for (int len=2;len<=n;len++){	//不必从1开始 
		for (int l=1;l<=n-len+1;l++){
			for (int k=l;k<l+len-1;k++){		//枚举中间点k 
				dp[l][l+len-1]=min(dp[l][l+len-1],dp[l][k]+dp[k+1][l+len-1]+qzh[l+len-1]-qzh[l-1]);
				//从l到r（l+len-1）的代价加上从l到r的所有数据 因为合并的代价为两堆石子的质量之和 
			}
		}
	}
	
//	for (int i=1;i<=n;i++){
//		for (int j=1;j<=n;j++){
//			cout << dp[i][j] <<" ";
//		}
//		cout << endl;
//	}
	cout << dp[1][n];		//输出 
}

#include<iostream>
#include<cstring>
using namespace std;
int n;
int a[1005];
int dp[1005][1005];
int sum[114514];
int main()
{
	memset(dp,0x3f,sizeof dp);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i][i]=0;
        sum[i]=sum[i-1]+a[i];
    }
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n-i+1;j++)
		{
			int l=j,r=j+i-1;
			for(int k=1;k<=n;k++)
			{
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
			}
		}
	}
	cout<<dp[1][n];
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int dp[310][310],l,a[310],n,s[310];
int main(){
	cin>>n;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i][i]=0;
		s[i]=s[i-1]+a[i];
	}
	for(int l=2;l<=n;l++){
		for(int i=1;i<=n-l+1;i++){
			int j=i+l-1;
			for(int k=i;k<j;k++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
			}
		}
	}
	cout<<dp[1][n];
}

随便点差评的题解

求不要点好评

#include<iostream>
#include<cstring>
using namespace std;
int n;
int a[1005];
int dp[1005][1005];
int sum[114514];
int main()
{
	memset(dp,0x3f,sizeof dp);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i][i]=0;
        sum[i]=sum[i-1]+a[i];
    }
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n-i+1;j++)
		{
			int l=j,r=j+i-1;
			for(int k=1;k<=n;k++)
			{
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
			}
		}
	}
	cout<<dp[1][n];
    return 0;
}