C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int w[N*2];
int dp[N*2][N*2];
int n;

int main(){
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> w[i];        
        w[i+n] = w[i];
    }

    for(int len = 3;len <= n+1;++len)
        for(int l = 1;l + len - 1 <= n*2;++l){
            int r = l + len - 1;
            for(int k = l+1;k < r;++k)
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + w[l] * w[r] * w[k]);
        }

    int ans = 0;
    for(int l = 1;l <= n;++l) ans = max(ans, dp[l][l+n]);
    cout << ans << endl;
}