【每日一题】加分二叉树 题解

Description

 一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：

 subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数

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

Solution

按照题意，很容易想到分治做法，构造一个函数 是求区间 的最优解
然后由 subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
可以得到 其中 为 中的一个节点
那么最终答案就是 , 类似于记忆化搜索的一种思想去解决
然后怎么输出前序遍历的结果呢?我们在记忆化搜索的时候维护一个
代表区间 的最优值取的是节点
那么我们前序遍历的时候只需要遍历 , ,
写一个函数递归输出即可

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll mod = 1e9 + 7;
const int N = 2e5 + 5;
ll a[35];
ll dp[35][35];
int root[35][35];
ll solve(int l, int r) {
  if(dp[l][r]) return dp[l][r];
  if(l == r) return a[l];
  if(r < l) return 1;
  for(int i = l; i <= r; i++) {
    ll p = solve(l, i - 1) * solve(i + 1, r) + a[i];
    if(p > dp[l][r]) {
      dp[l][r] = p;
      root[l][r] = i;
    }
  }
  return dp[l][r];
}
void print(int l, int r) {
  if(l > r) return ;
  if(l == r) {
    cout << l << ' ';
    return ;
  }
  cout << root[l][r]<< ' ';
  print(l, root[l][r] - 1);
  print(root[l][r] + 1, r);
}
int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  dp[1][n] = solve(1, n);
  cout << dp[1][n] << "\n";
  print(1, n);
  return 0;
}