题解

#include<bits/stdc++.h>
using namespace std;
const int MX=301;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    int s[MX];
    int dp[MX][MX];
    memset(dp,0x3f,sizeof(dp));
    cin>>n;
    for(int i=1;i<=n;i++){
    	int x;
    	cin>>x;
    	s[i]=s[i-1]+x;
    	dp[i][i]=0;
	}
	for(int len=1;len<=n;len++)
		for(int i=1;i<=n-len;i++){
			int j=i+len;
			for(int k=1;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]<<"\n";
    return 0;
}

大佬留下你的一个赞吧！