记录编号	445160	评测结果	AAAAA
题目名称	石子合并(加强版)	最终得分	100
用户昵称	liuyu	是否通过	通过
代码语言	C++	运行时间	0.250 s
提交时间	2017-09-05 11:58:17	内存使用	67.77 MiB

#include<bits/stdc++.h>
using namespace std;
int n,s[4204],f[4204][4204],sum[4203];
void init()
{
	scanf("%d",&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("stone3.in","r",stdin);
	freopen("stone3.out","w",stdout);
	init();
	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;
	  	f[i][r]=max(f[i+1][r],f[i][r-1]);
	  	f[i][r]+=sum[r]-sum[i-1];
	  }
	//int Min=1e9;
	for(int i=1;i<=n;i++)Max=max(Max,f[i][i+n-1]);
	printf("%d",Max);
	return 0;
}