题解

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[2N],ans,n,dp[2N][2N],b[2N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
a[i+n] = a[i];
}
//a[n2+1] = a[1];
for(int i=1;i<=2n;++i){
b[i] = a[i+1];
}
for(int len=2;len<=n;++len){
for(int l=1;l+len-1<=2*n;++l){
int r=l+len-1;
for(int i=l;i<r;++i){
dp[l][r] = max(dp[l][r],dp[l][i]+dp[i+1][r]+a[l]*b[i]*b[r]);

		}
		//cout<<dp[l][r]<<" ";
	}
}
for(int i=1;i<=n;++i){
	ans = max(ans,dp[i][i+n-1]);
}
cout<<ans;
return 0;

}