记录编号	164962	评测结果	AAAAA
题目名称	石子合并(加强版)	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.312 s
提交时间	2015-06-09 15:31:01	内存使用	130.57 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int sum[4002][4002],s[4502],f[4502][4025];//,cd[250][250];
int n,k,a[4520];
int main()
{   //memset(cd,30,sizeof(cd));
    freopen("stone3.in" ,"r",stdin ) ;
	freopen("stone3.out","w",stdout) ;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	 {
		scanf("%d",&k);
		a[i]=k;
		a[i+n]=k;
	 }
	for(int i=1;i<=2*n;++i)
			s[i]=s[i-1]+a[i];
	for(int i=1;i<=2*n;++i)
	 for(int j=i+1;j<=2*n;++j)
		sum[i][j]=s[j]-s[i-1];
	for(int i=2;i<=n;++i)
	 for(int j=1;j<=2*n-i+1;++j)
	 {
		 int k=i+j-1;
		 f[j][k]=max(f[j+1][k],f[j][k-1])+sum[j][k];
		 //cd[j][k]=min(cd[j+1][k],cd[j][k-1])+sum[j][k];
	 }
	int nmax=0,nmin=2500000;
	for(int i=1;i<=n;++i)
	{
		nmax=max(nmax,f[i][i+n-1]);
		//nmin=min(nmin,cd[i][i+n-1]);
	}
	//printf("%d\n",nmin);
	printf("%d",nmax);
    //system("pause");
}