记录编号	418084	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	liuyu	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-06-29 09:57:49	内存使用	0.47 MiB

#include<bits/stdc++.h>
using namespace std;
int n,s[204],f[204][204],sum[203];
void init()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]),s[n+i]=s[i];
		
	}
	for(int i=1;i<=2*n;i++)sum[i]+=sum[i-1]+s[i];
}
int main()
{
	freopen("stone2.in","r",stdin);
	freopen("stone2.out","w",stdout);
	init();
	for(int p=2;p<=n;p++)
	  for(int i=1;i+p-1<=2*n;i++)
	  {
	  	int r=i+p-1;
	  	f[i][r]=1e9;
	  	for(int k=i;k<r;k++)f[i][r]=min(f[i][r],f[i][k]+f[k+1][r]+sum[r]-sum[i-1]);
	  }
	int Min=1e9;
	for(int i=1;i<=n;i++)Min=min(Min,f[i][i+n-1]);
	cout<<Min<<endl;
	
	memset(f,0,sizeof(f));
	int Max=0;
	for(int p=2;p<=n;p++)
	  for(int i=1;i+p-1<=2*n;i++)
	  {
	  	int r=i+p-1;
	  	for(int k=i;k<r;k++)f[i][r]=max(f[i][r],f[i][k]+f[k+1][r]+sum[r]-sum[i-1]);
	  }
	//int Min=1e9;
	for(int i=1;i<=n;i++)Max=max(Max,f[i][i+n-1]);
	cout<<Max<<endl;
	return 0;
}