$\LARGE\color{orange}{刷题日记(算法提高课)}$

由于这道题只是给出了二叉树节点的中序遍历，而单靠一个中序遍历是无法确定一棵二叉树的

也就是说，题目所给的中序遍历实际上表示的是一堆二叉树的集合，基于此，我们就不能企图将所有的二叉树枚举出来再一一递归，这样不现实

我们可以考虑用动态规划的方法，因为动态规划实际上也是表示一个集合，并且是对暴力做法的一种优化

$f[i][j]$ 表示的集合为：中序遍历为 $[l,\ r]$ 的所有二叉树的集合，属性为所有二叉树当中加和的最大值

由于题目所给的是中序遍历，因此如果我们确定了根节点的话，根节点左边（不包括根节点）的就是左子树，右边同理

因此对于区间 $[l,\ r]$ ，我们通过枚举所有的根节点位置，进而可以得到 $f[l][r]$ 的值，即 $f[l][r]=max(f[l][r],f[l][root-1]\timmes f[root+1][r]+q[root])$

由于我们还需要输出这棵二叉树的前序遍历，因此我们还需要记录一下每个区间是从哪两个区间转移过来的，即需要记录每个区间的根节点，我们用 $g[l][r]$ 来表示

最后我们倒过来递归遍历整个区间即可

完整代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35;
int q[N], f[N][N], g[N][N];
int n;

void dfs(int l, int r)
{
    if(l > r) return;
    int root = g[l][r];
    cout << root << " ";
    dfs(l, root - 1);
    dfs(root + 1, r);
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> q[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] = q[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 + q[k];
                    if(score > f[l][r])
                    {
                        f[l][r] = score;
                        g[l][r] = k;
                    }
                }
        }
    }
    cout << f[1][n] << endl;
    dfs(1, n);
    return 0;
}