Miku

区间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;
}