题意

有一颗二叉树，树的每一个节点都有一个值，设他的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。
任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。
要求输出：
（1）tree的最高加分
（2）tree的前序遍历

输入描述

第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。

输出描述

第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。

解析

首先我们知道只靠中序遍历并不能确定一个二叉树，通过中序遍历我们可以知道根的左边是左子树，右边是右子树，并且在这个题目中中序遍历是连续的，也就是说我们可以得出这个左子树所在的区间，根，右子树所在的区间连在一起是一个连续区间，那么我们要求最高得分，首先来看这个记分规则，左子树的分数乘以右子树的分数加上根的分数，这么来看，首先我们要让左子树右子树的分数尽可能的个高，这么看我们把左子树右子树分开这个正好是区间dp哒，对于dp而言最重要的就是dp数组的含义哒，这里我们用二维数组dp[i][j]表示中序遍历[i，i+1，...j-1,j],的最大值，那么状态转移就是根节点值加上左子树最大乘右子树最大，在区间[i，j]中枚举全部的决策点k，计算到最大就是我们要的值，还有一个点就是要特判一下没有左右子树的情况。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }

const int N = 35;
ll dp[N][N], rt[N][N];
int a[N];

void dfs(int l, int r) {
    if (l > r)    return;
    int k = rt[l][r];
    printf("%d ", k);
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i)    a[i] = read();
    for (int len = 1; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1; 
            for (int k = l; k <= r; ++k) { 
                ll lson = k == l ? 1 : dp[l][k - 1];
                ll rson = k == r ? 1 : dp[k + 1][r];
                ll tmp = lson * rson + a[k];
                if (l == r)    tmp = a[k]; 
                if (tmp > dp[l][r]) {
                    dp[l][r] = tmp;
                    rt[l][r] = k;
                }
            }
        }
    }
    printf("%lld\n", dp[1][n]);
    dfs(1, n);
    return 0;
}