记录编号	416481	评测结果	AAATE
题目名称	石子合并(加强版)	最终得分	60
用户昵称	玉带林中挂	是否通过	未通过
代码语言	C++	运行时间	1.336 s
提交时间	2017-06-21 19:34:17	内存使用	15.66 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=2005;
const int inf=2147483647;
int dp[maxn][maxn],sum[maxn],st[maxn];   //dp[i][j]表示i到j最大分数，sum表示i到j石子个数
int n; 
int max(int a,int b)
{
	return a>b?a:b;
 } 
void Dp()
{
	for(int p=1;p<n;p++)//枚举合并区间长度   
        for(int i=1,j=i+p;(i<n*2) && (j<=n*2);i++,j=i+p)
		{//确定区间起终点   
            dp[i][j]=1<<30,dp[i][j]=0;  
            for(int k=i;k<j;k++)
			{  //枚举断点   
                dp[i][j]=max(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],dp[i][j]);  
            }  
        } 
	int ma_x=-inf;
    for(int i=1;i<=n;i++)
        ma_x=max(ma_x,dp[i][n+i-1]);
    printf("%d",ma_x);
}
int main()
{
	freopen("stone3.in","r",stdin);
	freopen("stone3.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&st[i]);
		st[i+n]=st[i];
	}
	for(int i=1;i<=n*2;i++)
	    sum[i]=sum[i-1]+st[i];
	Dp();
	return 0;
}