二刷提高课，题解目录在这里— 提高课的题解目录

注意题目的条件是符合中序遍历为1,2,3,4…n的二叉树
符合中序遍历但并未规定谁为根节点，所以我们用f[l][r]表示中序遍历为[l,r]的二叉树
所以我们直接在区间DP中枚举根节点即可

#include<iostream>
#include<cstring>
using namespace std;
const int N=50;
int w[N];
int f[N][N],g[N][N];
int n;
void dfs(int l,int r)
{
    if(l>r)return;
    int mid=g[l][r];
    cout<<mid<<" ";
    dfs(l,mid-1);
    dfs(mid+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][l]=w[l],g[l][l]=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 soce=left*right+w[k];
                    if(soce>f[l][r])
                    {
                        f[l][r]=soce;
                        g[l][r]=k;
                    }
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    dfs(1,n);
    return 0;
}