P1880 石子合并

#include <bits/stdc++.h>
using namespace std;
int a[301];
int dp[201][301];
int dp2[201][301];
int qzh[201];
int mx=0,mn=2e9;
int ans;
int main(){
	int n;scanf("%d",&n);
	memset(dp2,0x7f,sizeof(dp2));
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);a[i+n]=a[i];
	}
	for(int i=1;i<=n*2;i++)qzh[i]=qzh[i-1]+a[i],dp2[i][1]=0;;
	for(int len=2;len<=n;len++){
		for(int u=1;u+len-1<=n*2;u++){
			int v=u+len-1;
			for(int mid=u+1;mid<=v;mid++){
				dp[u][len]=max(dp[u][len],dp[u][mid-u]+dp[mid][v-mid+1]+qzh[v]-qzh[u-1]);
				dp2[u][len]=min(dp2[u][len],dp2[u][mid-u]+dp2[mid][v-mid+1]+qzh[v]-qzh[u-1]);
			}
			if(len==n){
				mx=max(mx,dp[u][len]);
				mn=min(mn,dp2[u][len]);
			}
		}
	}
	printf("%d\n%d",mn,mx);
}