题解

区间dp

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

int n;
int a[210],b[210];
int lw[210][210],up[210][210];

int main(){
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[i+n]=a[i]+b[i-1];
	}
	for(int i=1;i<=2*n;i++){
		b[i]=b[i-1]+a[i];
	}
	memset(lw,0x3f,sizeof lw);
	memset(up,-0x3f,sizeof up);
	for(int i=1;i<=2*n;i++){
		lw[i][i]=0;
		up[i][i]=0;
	}
	for(int len=1;len<=n;len++){
		for(int l=1;l+len-1<=2*n;l++){
			int r=l+len-1;
			for(int k=l;k<=r-1;k++){
				lw[l][r]=min(lw[l][r],lw[l][k]+lw[k+1][r]+b[r]-b[l-1]);
				up[l][r]=max(up[l][r],up[l][k]+up[k+1][r]+b[r]-b[l-1]);
			}
		}
	}
	int ma=-INT_MAX,mi=INT_MAX;
	for(int i=1;i<=n;i++){
		ma=max(ma,up[i][n+i-1]);
		mi=min(mi,lw[i][n+i-1]);
	}
	printf("%d\n%d",mi,ma);
	return 0;
}