Luogu-P1040-加分二叉树

题目 P1040 [NOIP2003 提高组] 加分二叉树

题目描述

设一个 $n$ 个节点的二叉树 $\text{tree}$ 的中序遍历为$(1,2,3,\ldots,n)$，其中数字 $1,2,3,\ldots,n$ 为节点编号。每个节点都有一个分数（均为正整数），记第 $i$ 个节点的分数为 $d_i$，$\text{tree}$ 及它的每个子树都有一个加分，任一棵子树 $\text{subtree}$（也包含 $\text{tree}$ 本身）的加分计算方法如下：

$\text{subtree}$ 的左子树的加分 $\times$ $\text{subtree}$ 的右子树的加分 $+$ $\text{subtree}$ 的根的分数。

若某个子树为空，规定其加分为 $1$，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为 $(1,2,3,\ldots,n)$ 且加分最高的二叉树 $\text{tree}$。要求输出

1. $\text{tree}$ 的最高加分。

2. $\text{tree}$ 的前序遍历。

思路：dp

dp表

使用二维的dp表，存放树的起点和终点。

• $dp[i][j]$ 的含义是：从 $i$ 到 $j$ 的树中，分数的最大值。

• $str[i][j]$ 的含义是：从 $i$ 到 $j$，并且使分数最大的树的前序遍历。

状态

• 初状态：

  • $dp$ 数组的初状态，即为题意中的空树分数为 $1$。

    考虑空树是不可能成立的 $dp[i][j]$，因此只需要将 $i>j$ 的部分置为 $1$ 即可。

    另外，由于循环计算时只需要考虑下标 $ \pm 1$ 的情形（见状态转移方程），因此，$dp$ 数组的初状态可为下列两种的任意一种：

    dp[i + 1][i] = 1;

    dp[i][i - 1] = 1;

    • $str$ 数组的初状态，即为树中只有一个节点的情况。

    str[i][i] = to_string(i);

• 状态转移方程：

  需要注意的是，$i$ 和 $j$ 并不能确定一个树，因此需要在 $i \sim j$ 中循环枚举根节点 $k$。

  $str$ 数组可能存在值为空的情况，因此需要判断字符串的长度是否为 $0$，如果不为 $0$ 则说明字符串包含数字，需要在头尾加空格。

  maxset(dp[i][j], dp[i][k - 1] * dp[k + 1][j] + score[k]);
  
  str[i][j] = str[k][k] + (str[i][k - 1].size() ? " " : "") + str[i][k - 1] + (str[k + 1][j].size() ? " " : "") + str[k + 1][j];

  • 需要注意的是，以上并非完整的方程，因为只有在 $dp$ 数组更新时才改变 $str$ 数组。所以应该先判断是否更新分数，再状态转移。

  • 题目中说叶子不考虑空子树，因此要特殊判断两支子树是否均为空（k == i == j）。

• 末状态：$dp[1][n]$ 为分数，$str[1][n]$ 为前序遍历。

AC Code

// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void minset(int &t, int other) {
    t = min(t, other);
}

inline void maxset(int &t, int other) {
    t = max(t, other);
}

const int inf = 0x7f7f7f7f;

const int N = 31;

unsigned int dp[N][N];
string str[N][N];
int score[N];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    for(int i = 1; i <= n; i++) {
        dp[i][i - 1] = dp[i + 1][i] = 1;
        str[i][i] = to_string(i);
    }
    for(int i = n; i >= 1; i--) {
        for(int j = i; j <= n; j++) {
            for(int k = i; k <= j; k++) {
                const unsigned int curr_score = !(k == i && k == j) * dp[i][k - 1] * dp[k + 1][j] + score[k];
                if(curr_score > dp[i][j]) {
                    dp[i][j] = curr_score;
                    str[i][j] = str[k][k] + (str[i][k - 1].size() ? " " : "") + str[i][k - 1] + (str[k + 1][j].size() ? " " : "") + str[k + 1][j];
                }
            }
        }
    }
    cout << dp[1][n] << '\n' << str[1][n] << endl;
    return 0;
}

补充

三维数组唯一确定树

如果用三维数组 $dp[i][j][k]$ 来确定树（$i \sim j$，根为 $k$），并不能简化状态转移。因为：

maxset(dp[i][j][k], dp[i][???][k - 1] * dp[k + 1][???][j] + dp[j][j][j]);

仍然需要遍历下标确定子树的根。

简化$str$的状态转移

简化方式

可以在有数字的字符串后面添加空格来避免判断。

简化后状态

• 初状态：

  str[i][i] = to_string(i) + " ";

• 状态转移方程：

  str[i][j] = str[k][k] + str[i][k - 1] + str[k + 1][j];

  • 需要注意的是，这种做法会在字符串末尾产生一个空格。

AC Code

// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void minset(int &t, int other) {
    t = min(t, other);
}

inline void maxset(int &t, int other) {
    t = max(t, other);
}

const int inf = 0x7f7f7f7f;

const int N = 31;

unsigned int dp[N][N];
string str[N][N];
int score[N];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    for(int i = 1; i <= n; i++) {
        dp[i][i - 1] = dp[i + 1][i] = 1;
        str[i][i] = to_string(i) + " ";
    }
    for(int i = n; i >= 1; i--) {
        for(int j = i; j <= n; j++) {
            for(int k = i; k <= j; k++) {
                const unsigned int curr_score = !(k == i && k == j) * dp[i][k - 1] * dp[k + 1][j] + score[k];
                if(curr_score > dp[i][j]) {
                    dp[i][j] = curr_score;
                    str[i][j] = str[k][k] + str[i][k - 1] + str[k + 1][j];
                }
            }
        }
    }
    cout << dp[1][n] << '\n' << str[1][n] << endl;
    return 0;
}

为什么用unsigned int？

普通$int$的最大值为$2^{31}-1$，即$2,147,483,647$。而本题的$ans\leq 4,000,000,000$，因此有可能爆$int$。（虽然用$int$也能过）