每日一题：加分二叉树 （树形dp/区间dp）

题意

有一颗二叉树，树的每一个节点都有一个值，设他的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。

任一棵子树subtree（也包含tree本身）的加分计算方法如下：

subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。

要求输出：（1）tree的最高加分（2）tree的前序遍历

solution

符合条件的二叉树是加分最高的二叉树，它的总分依题意得 总分 = 左子树分数 * 右子树分数 + 根节点分数 ，想要总分最高，左右子树的分数应当也分别取最高。

题目中给出的节点序号根据二叉树的中序遍历排列，$dp[l][r]$ （l<r） 表示从节点 $l$ 到节点 $r$ 所构成的子树的最高加分。设$k(l \le k \le r)$为该子树的根节点，通过枚举当前 $[l,r]$ 某点为根来取得不同的左右子树和根节点分数，维护最大值。

状态转移方程：

$dp[i][j]=max(dp[i][j],dp[i][k-1]*dp[k+1][r]+dp[k][k])$

最后维护一个 $root$ 数组表示节点 $l-r$ 最高分子树的根即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 35;

int n, root[N][N];
ll dp[N][N];

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

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> dp[i][i];
    dp[i][i - 1] = 1;
    dp[i + 1][i] = 1;
    root[i][i] = i;
  }
  for (int i = 1; i <= n; i++) {
    for (int l = 1; l + i <= n; l++) {
      int r = l + i;
      for (int k = l; k <= r; k++) {
        int tmp = dp[l][k - 1] * dp[k + 1][r] + dp[k][k];
        if (dp[l][r] < tmp) {
          dp[l][r] = tmp;
          root[l][r] = k;
        }
      }
    }
  }
  cout << dp[1][n] << '\n';
  dfs(1, n);
  return 0;
}