区间dp（模板2）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const mod=19650827;
int const INF=0x7f7f7f7f;
int const N=2e2+7;
int n;
ll f[N][N],f2[N][N],a[N];  //f[i][j]表示合并[i,j]的最大分数
int main(){
	cin >> n;
	memset(f2,0x7f,sizeof f2);
	for(int i=1;i<=n;++i){
		cin >> a[i];
		a[i+n]=a[i];
		f2[i][i]=f2[n+i][n+i]=0;
	}
	for(int i=1;i<=2*n;++i) a[i]+=a[i-1];
	if(n==1){
		cout << "0\n0";return 0;
	}
	ll ans=0,ans2=INF;
	for(int l=2;l<=n;++l){
		for(int i=1;i+l-1<=2*n;++i){
			int j=i+l-1;
			for(int k=i;k+1<=j;++k){   //枚举分界点
				f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
				f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+a[j]-a[i-1]);
			}
			if(l==n) ans=max(ans,f[i][j]),ans2=min(ans2,f2[i][j]);
		}
	}
	cout << ans2 << "\n" << ans;
	return 0;
}