记录编号	248327	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	水墨青花	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2016-04-10 11:56:16	内存使用	0.53 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

void Read();
void Work();

int fn[201][201];
int fx[201][201];
int n;
int a[201];

int main()
{
	freopen("stone2.in","r",stdin);
	freopen("stone2.out","w",stdout);
	
	memset(a,0,sizeof(a));
	memset(fx,0,sizeof(fx));
	memset(fn,0,sizeof(fn));
	
	Read();
	Work();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

void Read()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i+n]=a[i];
	}
	for(int i=1;i<=n*2;i++)
	{
		a[i]+=a[i-1];
	}
}

void Work()
{
	for(int d=2;d<=n;d++)	//d：区间长度 
	{
		for(int i=1;i<n*2-d+1;i++)	//i：起点 
		{
			int j=i+d-1;	//j：终点 
			fn[i][j]=0x7fffffff;
			for(int k=i;k<j;k++)	//k：断点 
			{
				fn[i][j]=min(fn[i][j],fn[i][k]+fn[k+1][j]+a[j]-a[i-1]);
				fx[i][j]=max(fx[i][j],fx[i][k]+fx[k+1][j]+a[j]-a[i-1]);
			}
		}
	}
	
	int maxn=0;
	int minn=0x7fffffff;
	for(int i=1;i<=n;i++)
	{
		maxn=max(maxn,fx[i][i+n-1]);
		minn=min(minn,fn[i][i+n-1]);
	}
	
	printf("%d\n%d",minn,maxn);
}