记录编号	437118	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]能量项链	最终得分	100
用户昵称	据说这是zzy	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2017-08-13 17:22:02	内存使用	15.66 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int n,mx;
int a[2005],f[2005][2005];
int main()
{
	freopen("energy.in","r",stdin);
	freopen("energy.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)//
        a[n+i]=a[i];
    //令f[i][j],j-i+1是几个数，且是几个珠子 
    for(int len=2;len<=n;len++)//表示几个珠子 
        for(int i=1;i+len-1<2*n;i++)
        {
            int j=i+len-1;
            for(int k=i;k<j;k++)//
            f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
        }
    for(int i=1;i<=n;i++)
        if(f[i][i+n-1]>mx) mx=f[i][i+n-1];
    cout<<mx<<endl;

}