记录编号	415802	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]能量项链	最终得分	100
用户昵称	liuyu	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2017-06-18 19:16:29	内存使用	16.50 MiB

#include<bits/stdc++.h>
using namespace std;
int N,n[303],f[103][203][203];
int main()
{
	freopen("energy.in","r",stdin);
	freopen("energy.out","w",stdout);
	cin>>N;
	for(int i=1;i<=N;i++)
	  scanf("%d",&n[i]);
	for(int i=1;i<=N;i++)n[N+i]=n[i],n[2*N+i]=n[i];  
	for(int i=1;i<=3*N;i++)
	  f[2][i][i+1]=n[i]*n[i+1]*n[i+2];
	  
	//f[2][2*N-1][2*N]=n[2*N-1]*n[2*N]*n[1];
	
	for(int p=3;p<=N;p++)
	  for(int i=1;i+p<=3*N;i++)
	    for(int k=1;k<p;k++)             // f[1][1][1]+f[2][2][3]
	      f[p][i][p+i-1]=max(f[p][i][p+i-1],f[k][i][i+k-1]+f[p-k][k+i][p+i-1]+n[i]*n[k+i]*n[p+i]);
	int Max=0;
	for(int i=1;i<=2*N;i++)Max=max(Max,f[N][i][N+i-1]);
	cout<<Max;
	return 0;
}