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

思路：

• $1. 状态表示$
  $集合：区间[l,r]内的节点合并后可以得到的分数$
  $属性：\max$

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

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 30;

int n;
int w[N];
int f[N][N];
int g[N][N];

void dfs(int l,int r)
{
    if(l>r) return;
    cout<<g[l][r]<<' '; //输出根节点
    dfs(l,g[l][r]-1); //递归左边
    dfs(g[l][r]+1,r); //递归右边
}

int main()
{
    cin>>n;

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

    for(int len=1;len<=n;len++) //枚举区间长度
        for(int l=1;l+len-1<=n;l++) //枚举左端点
        {
            int r=l+len-1; //右端点
            if(len==1)
            {
                f[l][r]=w[l];
                g[l][r]=l;
            }
            else 
            {
                for(int k=l;k<=r;k++) //枚举分界点
                {
                    int left=k==l?1:f[l][k-1];
                    int right=k==r?1:f[k+1][r];
                    int score=left*right+w[k];
                    if(f[l][r]<score)
                    {
                        f[l][r]=score;
                        g[l][r]=k;
                    }
                }
            }
        }

    cout<<f[1][n]<<endl;

    dfs(1,n);

    return 0;
}