记录编号	420006	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]能量项链	最终得分	100
用户昵称	Hyoi_iostream	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-07-03 18:54:32	内存使用	0.00 MiB

/* 
状态定义：dp[i][j]表示合并i~j，得到的最大能量 
转移方程：dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[j+1]*a[k+1]); 
边界：答案为max{dp[i][i+n-1]}  
*/  
#include<cstdio>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
const int maxn = 200 + 10 ;  
int a[maxn],dp[maxn][maxn];  
int n,maxx=-1;  
inline int Main(){  
    /*#ifndef DEBUG  
        string FileName="energy";  
        freopen((FileName+".in").c_str(),"r",stdin);  
        freopen((FileName+".out").c_str(),"w",stdout);  
    #endif  */
    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];//预处理使得环形转化为链形   
    }  
    for(int i=n*2-1;i>=1;i--)//枚举起点，倒序保证所需状态都已经计算出来  
        for(int j=i;j<=i+n-1;j++)//枚举终点   
            for(int k=i;k<=j-1;k++)//枚举断点 （以上断链至少长1，注意各种+1 -1）  
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[j+1]*a[k+1]);  
    for(int i=1;i<=n;i++) maxx=max(maxx,dp[i][i+n-1]);//寻找从哪个地方断开整条项链，能量最大   
    printf("%d",maxx);  
	fclose(stdin);
	fclose(stdout);
	return 0; 
}  
int work=Main();
int main(){;}