$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：区间[l,r]内的珠子合并后的得分$
  $属性：\max$

• $2. 状态转移$
  $f[l][r]=\max\{f[l][k]+f[k][r]+w[l]\cdot w[k]\cdot w[r] \}\ (l< k < r)$

本题思路： $最大值=\max\{f[i][i+n]\}\ (1\le i\le n)$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 210;

int n;
int w[N];
int f[N][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++) //枚举区间长度，当区间长度<=2时不需要合并
        for(int l=1;l+len-1<=n*2;l++) //枚举左端点
        { 
            int r=l+len-1; //右端点
            for(int k=l+1;k<r;k++) //枚举该区间的分界点
                f[l][r]=max(f[l][r],f[l][k]+f[k][r]+w[l]*w[k]*w[r]);
        }

    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i][i+n]);

    cout<<res<<endl;

    return 0;
}