解题思路

区间dp
又又又是区间dp；看来是个极其重要的动态规划模型吖！
这里给出的数据规模小于等于30，很明显可以开下很多维的数组，运行的时间复杂度也很高。
题目第二行给出的是每个节点的初始值。我们要找到一个前序序列，让题目给出的函数值最大。
根据题目给出中序序列为 1 2 3 4 5 6 7 …… n那么树的样子一定是固定了的，与平衡树类似左子树的全部节点一定小于根节点，右子树大于。
那么在知道这个前提下就很好去进行递推了。首选区间dp。
从这里看出允许使用不带优化的区间dp，直接 怼上去就行了
我们二维数组 dp[i][j]表示从 i 到 j 满足题目中序遍历为(i i+1 …… j)的最大值。
那么状态转移就是根节点值加上左子树最大乘右子树最大，在区间（i，j）中枚举全部的决策点k，计算到最大即可。
注意特判没有左右子树的情况，别多加了个1。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
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]; //特判没有子树的情况，不然会多加1
                if (tmp > dp[l][r]) {
                    dp[l][r] = tmp;
                    rt[l][r] = k;
                }
            }
        }
    }
    printf("%lld\n", dp[1][n]);
    dfs(1, n);
    return 0;
}