记录编号	171433	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]能量项链	最终得分	100
用户昵称	落尘	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2015-07-19 14:45:38	内存使用	0.47 MiB

#include <iostream>
#include <cstdio>
using namespace std;
int N;
int a[202],tot;
int f_max[201][201];
int main(){
	ios::sync_with_stdio(false);
	freopen("energy.in","r",stdin);
	freopen("energy.out","w",stdout);
	cin>>N;
	for(int i=1;i<=N;i++) 
		cin>>a[i],a[i+N]=a[i];
	a[2*N+1]=a[1];
	for(int d=2;d<=N;d++)
		for(int i=1;i<=2*N-d+1;i++){
			int j=i+d-1,kk=i;
			for(int k=i;k<j;k++){
				if(f_max[i][k]+f_max[k+1][j]+a[i]*a[k+1]*a[j+1]>f_max[i][j]) 
					f_max[i][j]=f_max[i][k]+f_max[k+1][j]+a[i]*a[k+1]*a[j+1];
			}
			if(f_max[i][i+N-1]>tot)
				tot=f_max[i][i+N-1];
		}
	cout<<tot<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}