思路

区间DP模板题。

代码

#include<bits/stdc++.h>
using namespace std;

int n,a[505],mx[505][505],mi[505][505],sum[505];
	
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	} 
	sum[0]=0; 
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	memset(mx,0,sizeof(mx));
	memset(mi,127/3,sizeof(mi));
	for(int i=1;i<=n;i++) mi[i][i]=0;
	for(int len=2;len<=n;len++){
		for(int l=1;l<=n-len+1;l++){
			int r=l+len-1;
			for(int k=l;k<r;k++){
				mx[l][r]=max(mx[l][r],mx[l][k]+mx[k+1][r]+sum[r]-sum[l-1]);
				mi[l][r]=min(mi[l][r],mi[l][k]+mi[k+1][r]+sum[r]-sum[l-1]);
			}
		}
	}
	int maxx=-10000000,minn=10000000;
	for(int i=1;i<=n;i++){
		maxx=max(maxx,mx[i][i+n-1]);
		minn=min(minn,mi[i][i+n-1]);	
	}
	cout<<minn<<endl;
	//cout<<maxx<<endl;
	return 0;
}