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

#include<fstream>
using namespace std;
 
namespace cat{
	const int maxn = 100<<1 ;
	int f[maxn+10][maxn+10],b[maxn+10];
	int n,ans=0;
	int doo(){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",b+i),b[n+i]=b[i];
		int len = (n<<1)-1 ;
	//	for(int i=1;i<=len;i++) printf("%d ",b[i]);
	//	printf("\n");
	    for(int j=2;j<=len;j++)  
	        for(int i=j-1;i>=1 && j-i<n;i--){
				for(int k=i;k<j;k++)
				//for(int k=d[i][j-1];k<=d[i+1][j];k++)
				{	
					//if( k == j ) continue ;
					
					if(f[i][j] < f[i][k]+f[k+1][j]+b[i]*b[k+1]*b[j+1]){
						f[i][j]=f[i][k]+f[k+1][j]+b[i]*b[k+1]*b[j+1];
						//d[i][j] = k;
					}
						
				}
				if(ans < f[i][j]) ans=f[i][j];
			}
		printf("%d",ans);
		return 0;
	}
}
FILE *___ = freopen("energy.in","r",stdin);
FILE *_=freopen("energy.out","w",stdout);
int ans = cat::doo();
int main(){;}