思路：
n的范围很小。所以考虑记忆化搜索
dp[l][r]表示这棵树中序遍历中，第l个节点到第r个节点为一棵子树的得分最大值。
那么只需要枚举l到r中每一个点作为根节点即可。
容易得到方程如下
dp[l][r]=max(dp[l][r],dp[l][i-1]*dp[i+1][r]+a[i])
其中l≤i≤r
因为最后输出不仅仅是要最大得分，还需要输出这棵树的前序遍历。
我们现在已经知道中序遍历为1，2，3，4，5.....n要想知道前序遍历只需要知道每个区间的根节点是什么。然后根据根节点去左右dfs即可。
所以再开一个根节点数组root[l][r]表示区间l到r选择的根节点是什么。
在记忆化搜索的时候，注意dfs的边界问题，比如可能出现l>i-1、i+l>r这样，这意味着该树为空树，赋值为1然后return即可。
还有l=r的时候，其实就是遍历到了叶子节点，得分自然就是a[l]
注意开ll

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
ll a[35];
ll dp[35][35];
int root[35][35];
void dfs1(int l,int r){
    if(l==r){
        dp[l][r]=a[l];
        root[l][r]=l;
        return ;
    }
    if(l>r) {
        dp[l][r]=1;
        return ;
    }
    if(dp[l][r]==0){
        for(int i=l;i<=r;i++){
             dfs1(l,i-1);
             dfs1(i+1,r);
             ll q=dp[l][i-1]*dp[i+1][r]+a[i];
             if(q>dp[l][r]){
                dp[l][r]=q;
                root[l][r]=i;
             }
             ans=max(ans,dp[l][r]);
        }
    }
}
void dfs2(int l,int r){
    if(l>r) return ;
    cout<<root[l][r]<<" ";
    dfs2(l,root[l][r]-1);
    dfs2(root[l][r]+1,r);
}
int main(){

    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs1(1,n);
    cout<<ans<<endl;
    dfs2(1,n);
    return 0;
}