记录编号	248491	评测结果	AAAAA
题目名称	石子合并(加强版)	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	1.008 s
提交时间	2016-04-10 15:44:28	内存使用	64.47 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>

using namespace std;

int f[4100][4100],w[4100],s[4100]; 

int max(int a,int b,int c)
{
	if(a>b && a>c) return a;
	if(b>a && b>c) return b;
	if(c>a && c>b) return c;
	else return a;
}

int main()
{
	freopen("stone3.in","r",stdin);
	freopen("stone3.out","w",stdout);
	memset(f,0,sizeof(f));
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
		s[i]=s[i-1]+w[i];
		f[i][i]=f[i+n][i+n]=0;
	}
	for(int i=1;i<=n;i++)
		s[i+n]=s[i+n-1]+w[i];
	int len=n*2,k;
	for(int i=len-1;i>=1;i--){
		for(int j=i+1;(j<=len && j<=i+n-1);j++){
			f[i][j]=max(f[i][i]+f[i+1][j]+s[j]-s[i-1],f[i][j-1],f[i][j-1]+f[j][j]+s[j]-s[i-1]);
		}
	}
	int ans=-1;
	for(int i=1;i+n-1<=len;i++)
		if(f[i][i+n-1]>ans) ans=f[i][i+n-1];
		
	printf("%d",ans);
	return 0;
		
	
}