记录编号	312751	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	Janis	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2016-09-27 15:04:07	内存使用	1.90 MiB

/*
状态定义：dp[i][j]表示合并i到j时的最大得分
转移方程：dp[i][j]=max(dp[i][k]+dp[k+1][j]+sum_stone[i][j],dp[i][j])
边界：max{dp[i][n+i-1]}为答案
*/ 
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=500;
int sum[maxn],dp[maxn][maxn][2],st[maxn];//0 for min,1 for max
int n;

void Init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&st[i]);
		st[i+n]=st[i];
	}
	for(int i=1;i<=n*2;i++)sum[i]=sum[i-1]+st[i];
}
void DP(){
	for(int p=1;p<n;p++)
		for(int i=1,j=i+p;(i<n*2) && (j<=n*2);i++,j=i+p){
			dp[i][j][0]=1<<30,dp[i][j][1]=0;
			for(int k=i;k<j;k++){
				dp[i][j][0]=min(dp[i][k][0]+dp[k+1][j][0]+sum[j]-sum[i-1],dp[i][j][0]);
				dp[i][j][1]=max(dp[i][k][1]+dp[k+1][j][1]+sum[j]-sum[i-1],dp[i][j][1]);
			}
			
		}
	int _max=-1,_min=1<<30;
	for(int i=1;i<=n;i++){
		_max=max(_max,dp[i][n+i-1][1]);
		_min=min(_min,dp[i][n+i-1][0]);
	}
	printf("%d\n%d",_min,_max);
}
int main()
{
	#ifndef DEBUG
		string FileName="stone2";
		freopen((FileName+".in").c_str(),"r",stdin);
		freopen((FileName+".out").c_str(),"w",stdout);
	#endif
	Init();
	DP();
}