记录编号	105911	评测结果	AAAAA
题目名称	石子合并(加强版)	最终得分	100
用户昵称	return 0；	是否通过	通过
代码语言	C++	运行时间	0.149 s
提交时间	2014-06-12 19:08:47	内存使用	61.41 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[4001],s[4001];
int f[4001][4001];
int nmax=0,tot;
void init();
void dp(); 
int main()
{
	freopen("stone3.in","r",stdin);
	freopen("stone3.out","w",stdout);
	init();
	dp();
}
void init()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[n+i]=a[i];
	}
	for(int i=1;i<=2*n;i++)
	{
		s[i]=s[i-1]+a[i];

	}
}
void dp()
{
	for(int d=2;d<=n;d++)
	{
		for(int i=1;i<=2*n-d+1;i++)
		{
			int zd=i+d-1;
			f[i][zd]=max(f[i+1][zd],f[i][zd-1]);
			f[i][zd]+=s[zd]-s[i-1];

		}
		
	}
	for(int i=1;i<=n;i++)
	{
		nmax=max(f[i][n+i-1],nmax);
	}
	cout<<nmax;
}