区间dp模板,记得longlong
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n;
long long a[201];
long long b[201];
long long dp[201][201];
long long ans;
int main(){
scanf("%lld",&n);
for(long long i=1;i<=n;++i){
scanf("%lld",&a[i]);
a[n+i]=a[i];
}
for(long long i=1;i<=2*n;++i){
b[i]=a[i+1];
}
b[2*n]=a[1];
for(long long i=2;i<=n;i++){
for(long long j=1;j+i-1<=2*n;++j)
for(long long k=j;k<j+i-1;++k){
dp[j][j+i-1]=max(dp[j][j+i-1],dp[j][k]+dp[k+1][j+i-1]+a[j]*b[j+i-1]*b[k]);
}
}
for(long long i=1;i<=n+1;++i){
ans=max(ans,dp[i][i+n-1]);
}
cout<<ans;
return 0;
}