记录编号	383093	评测结果	AAAAA
题目名称	石子合并(加强版)	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.175 s
提交时间	2017-03-15 08:59:20	内存使用	123.04 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int max(int x,int y)
{
    if(x>y)
      return x;
    else
      return y;
}

int n;
int cun[4010];
int a[4011][4011];
int fma[4010][4010];
//int fmi[4010][4010];
int main()
{
    freopen("stone3.in","r",stdin);
    freopen("stone3.out","w",stdout);
   // memset(fmi,0x3f,sizeof(fmi));
    
    cin>>n;
    for(int i=1;i<=n;i++)
    {  
            cin>>cun[i];
            //fmi[i][i]=0;
            a[i][i]=cun[i];
            
            //if(i!=n)
            //{
                    a[i+n][i+n]=a[i][i];
                    cun[i+n]=cun[i];
                   // fmi[i+n][i+n]=0;
            //}
           
            
    }
    
    for(int i=1;i<=2*n;i++)
      for(int j=i+1;j<=2*n;j++)
      {  a[i][j]=a[i][j-1]+cun[j];}
    
    for(int i=2*n;i>=1;i--)
      for(int j=i+1;j<=2*n;j++)
        //for(int k=i;k<=j-1;k++)
        {
                fma[i][j]=max(fma[i+1][j],fma[i][j-1])+a[i][j];
                //fmi[i][j]=min(fmi[i+1][j],fmi[i][j-1])+a[i][j];
        }
    int ans1=0,ans2=0x7fffffff;
    for(int i=1;i<=n;i++)
    {
            ans1=max(ans1,fma[i][i+n-1]);
            //ans2=min(ans2,fmi[i][i+n-1]);
    }
    cout<<ans1;
   // while(1);
    return 0;
}