记录编号	120243	评测结果	AAAAA
题目名称	石子合并(加强版)	最终得分	100
用户昵称	Ezio	是否通过	通过
代码语言	C++	运行时间	0.275 s
提交时间	2014-09-15 19:49:07	内存使用	49.13 MiB

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#define For(st,ed,i) for(int i=st;i<=ed;++i)
#define Fordown(st,ed,i) for(int i=st;i>=ed;--i)
#define start(a,flag) memset(a,flag,sizeof(a));
const int INF=0x7fffffff;
using namespace std;
int s[4001],v[4001];
int f[4001][4001];
int n,r1=0;
int dis(int i,int j){
    return s[j]-s[i-1];
}
int main(){
    freopen("stone3.in","r",stdin);
    freopen("stone3.out","w",stdout);
    cin>>n;int ln=n+n;
    For(1,n,i){
        scanf("%d",&v[i]);
        v[n+i]=v[i];
    }
    For(1,ln,i)s[i]=s[i-1]+v[i];
    For(2,n,p)For(1,ln-p+1,i){
        int zd=i+p-1;
        f[i][zd]=max(f[i+1][zd],f[i][zd-1]);
        f[i][zd]+=s[zd]-s[i-1];
    }
    For(1,n,i)r1=max(r1,f[i][i+n-1]);
    cout<<r1<<endl;
    //system("pause");
    return 0;
}