一道很水的区间DP,环拆链并复制一倍就好了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=105;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
} 
int f[N<<1][N<<1],a[N];
int main()
{
    int n;qr(n);
    for(int i=1;i<=n;i++)qr(a[i]),f[i+n][i+n]=f[i][i]=0,a[i+n]=a[i];
    for(int k=2;k<=n;k++)
        for(int i=1;i<=2*n-k+1;i++)
        {
            int j=i+k-1;
            for(int mid=i;mid<j;mid++)
                f[i][j]=max(f[i][j],f[i][mid]+f[mid+1][j]+a[i]*a[mid+1]*a[j+1]);
        }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,f[i][i+n-1]);
    qw(ans);puts("");
    return 0;
}