记录编号	308067	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]能量项链	最终得分	100
用户昵称	coolkid	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-09-16 20:20:46	内存使用	0.54 MiB

//dp[i][j]=max{dp[i][j],dp[i][k]*dp[k+1][j]*A[k]+dp[i][k]+dp[k+1][j]}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=120;

int dp[MAXN<<1][MAXN<<1],A[MAXN<<1];
int n;

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]),A[i+n]=A[i];
	
	memset(dp,0,sizeof(dp));
	
	int ans=-1;
	int n2=n<<1;
	for(int j=2;j<=n2;j++)
		for(int i=j-1;i>=1&&j-i+1<=n;i--)
			for(int k=i;k<j;k++){
				dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+A[i]*A[j+1]*A[k+1]);
				ans=max(ans,dp[i][j]);
//				printf("A[i]:%d A[j+1]:%d A[k]:%d\n",A[i],A[j+1],A[k+1]);
//				printf("dp[%d][%d]=%d\tk:%d\n",i,j,dp[i][j],k);
			}
	printf("%d\n",ans);
	return 0;
	
}