记录编号	68858	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]能量项链	最终得分	100
用户昵称	老师好~~~	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2013-08-31 18:02:23	内存使用	0.46 MiB

#include<fstream>
using namespace std;
ifstream fin("energy.in");
ofstream fout("energy.out");
int f[300][300];//f[i][j]代表从第i个珠子到第j个珠子释放后的最大能量
int b[300];
int n;
int maxn=0;
int main()
{
	int i,j,k;fin>>n;for(i=1;i<=n;i++) {fin>>b[i];b[n+i]=b[i];}
    for(j=2;j<=2*n-1;j++)  
        for(i=j-1;i>=1&&j-i<n;i--)
            {for(k=i;k<j;k++)
			{	if(f[i][k]+f[k+1][j]+b[i]*b[k+1]*b[j+1]>f[i][j])
					f[i][j]=f[i][k]+f[k+1][j]+b[i]*b[k+1]*b[j+1];}
			if(f[i][j]>maxn)
				maxn=f[i][j];
		}
	fout<<maxn<<endl;
	return 0;
}