[vijos1312]——[能量项链]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
template <class _T> inline void read(_T &_x) {
	int _t; bool _flag=false;
	while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
	if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
	while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
	if(_flag) _x=-_x;
}
const int maxn=105;
int n;
LL dp[maxn<<1][maxn<<1],ans;
struct node{
	int l,r;
}d[maxn<<1];
int main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(d[i].l);d[i+n].l=d[i].l;
		d[i-1].r=d[i+n-1].r=d[i].l;
	}
	for(int len=1;len<=n;len++){
		for(int l=1,r;(r=l+len-1)<2*n;l++){
			for(int k=l;k<r;k++){
				dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+d[l].l*d[r].r*d[k].r);
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i][i+n-1]);
	}
	printf(
	return 0;
}