【每日一题】【5月13日】加分二叉树

题意：

给定一棵含 $n$ 个节点的二叉树，其节点编号为 $1$ 到 $n$ 。二叉树的中序遍历为 $(1, 2, ..., n)$ 。每个节点有一个分数 $d_i$ 。

任一棵子树subtree（也包含tree本身）的加分计算方法为：
subtree的左子树的加分 $\times$ subtree的右子树的加分＋subtree 的根的分数。

若左右子树中某一子树为空，规定其分数为 1。
若左右子树都为空（即叶节点），则分数为叶节点本身的分数。

求分树最高的 tree。

解法：

对二叉树的概念和二叉树的中序遍历有一定了解的话，就很容易得到这样的性质：
二叉树的中序遍历可以不断递归划分成：（左子树）根节点（右子树）。
比如样例输出的那棵二叉树：

$1, 2, 3, 4, 5$ 根节点为 $3$ ，则可以划分成 $(1, 2), 3, (4, 5)$ 。

$1, 2$ 根节点为 $1$ ，则划分成 $(), 1, (2)$ 。

$4, 5$ 根节点为 $4$ ，则划分成 $(), 4, (5)$ 。

有了这个最关键的性质中序遍历不断递归划分成（左子树）根节点（右子树）这样的结构。

那么这道题的解法也很自然的出来了：区间 dp。

$dp[l][r]$ 表示编号从 $l$ 到 $r$ 构成的二叉树的分数的最大值。
枚举根节点 $k(l \leq k \leq r)$ 即可更新 $dp[l][r]$ 。

再考虑一下边界条件，就可以按题意写出 $dp$ 方程：

$dp[l][r] =\left\{ \begin{aligned} &1 &(l = r + 1)&\\ &a[l] &(l = r)&\\ &max(dp[l][k-1] \times dp[k+1][r] + a[k]) &(l < r \space \& \space l \leq k \leq r)& \end{aligned} \right.$

题目需要输出二叉树的前序遍历。
可以再开一个数组，用 $pre[l][r]$ 表示编号从 $l$ 到 $r$ 构成的二叉树的根节点编号。
在 $dp$ 转移的时候记录一下就可以了。
最后 dfs 输出前序遍历。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 35;
using uint = unsigned int;
uint dp[N][N], pre[N][N], a[N], n;
void dfs(int l, int r) {
    if(l > r) return;
    int k = pre[l][r];
    cout << k << " ";
    dfs(l, k - 1);
    dfs(k + 1, r);
}
int main() {
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            dp[i][j] = 1;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) {
        dp[i][i] = a[i];
        pre[i][i] = i;
    }
    for(int len = 2; len <= n; len++) 
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = 0;
            for(int k = i; k <= j; k++) { 
                uint v = dp[i][k - 1] * dp[k + 1][j] + a[k];
                if(dp[i][j] < v) {
                    dp[i][j] = v;
                    pre[i][j] = k;
                }
            }
        }
    cout << dp[1][n] << endl;
    dfs(1, n);
    return 0;
}