记录编号	323738	评测结果	AAAAA
题目名称	石子合并(加强版)	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.155 s
提交时间	2016-10-17 06:25:12	内存使用	77.73 MiB

#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define Begin freopen("stone3.in","r",stdin);freopen("stone3.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
using namespace std;
const int maxn=4505;
int f[maxn][maxn],sum[maxn];
int n;
void Init();

int main(){
    Begin
    Init();
    //End
    //system("pause");
    return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&sum[i]),sum[n+i]=sum[i],sum[i]+=sum[i-1];
	for(int i=n+1;i<=2*n;i++)sum[i]+=sum[i-1];
	for(int d=2;d<=n;d++){
		for(int i=1;i<=2*n-d+1;i++){
			int j=i+d-1;
			f[i][j]=max(f[i+1][j],f[i][j-1])+sum[j]-sum[i-1];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans=max(ans,f[i][n+i-1]);
	printf("%d\n",ans);
}