记录编号	106553	评测结果	AAAAA
题目名称	石子合并(加强版)	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2014-06-14 19:40:03	内存使用	61.37 MiB

#include <cstdio>

#define  maxn     4001

int n ;
int ans = 0 ;
int sum[maxn] ;
int f[maxn][maxn] = {0};

int main()
{
	freopen("stone3.in" ,"r",stdin ) ;
	freopen("stone3.out","w",stdout) ;
	scanf("%d", &n ) ;
	for (int i = 1 ; i <= n ; i ++ )
	{
		scanf("%d", &ans ) ;
		sum[i] = sum[i-1] + ans ;
	}
	for (int i = n ; i < 2*n ; i ++ )
		sum[i+1] = sum[i] + sum[i-n+1] - sum[i-n] ;
	for (int d = 2 ; d <= n ; d ++ )
	{
		for (int i = 1 ; i <= 2*n-d+1 ; i ++ )
		{
			if (f[i+1][i+d-1] > f[i][i+d-2])
			  f[i][i+d-1] = f[i+1][i+d-1] ;
            else
			  f[i][i+d-1] = f[i][i+d-2] ;
           	f[i][i+d-1] += (sum[i+d-1]-sum[i-1]) ;
		}
	}
	for (int i = 1 ; i <= n ; i ++ )
	{
		if (f[i][i+n-1] > ans) ans = f[i][i+n-1] ;
	}
	printf("%d\n",ans);
	//return 0 ;
}