能量项链

#include<bits/stdc++.h>
using namespace std;
#define N 210
typedef long long ll;
typedef pair<ll,ll> PII;
PII w[N];
ll n,a[N],f[N][N];
int main()
{
    cin>>n;
    memset(f,-0x3f,sizeof f);
    for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];//将环形拆成链形
    for(int i=1;i<2*n;i++)   
    {
        w[i]={a[i],a[i+1]};//用pair记录每个珠子的头尾标记
        f[i][i]=0;
    }
    f[2*n][2*n]=0;
    for(int l=2;l<=n;l++)//枚举长度
    {
        for(int i=1;i<=2*n-l;i++)//枚举起点
        {
            int j=i+l-1;//计算终点
            for(int k=i;k<j;k++)//枚举状态，即分割点,假如i=1,j=5,k=3,就是合并1-3号珠子（1）和4-5珠子（2）的最小能量，合并（1）（2）所得的能量为w[i].first*w[k].second*w[j].second
            {
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+w[i].first*w[k].second*w[j].second);
            }
        }
    }
    ll maxx=0;
    for(int i=1;i<=n;i++)
        maxx=max(maxx,f[i][i+n-1]);
    cout<<maxx;
}