题解：P1040 [NOIP 2003 提高组] 加分二叉树

给定一个含有

n

个结点的二叉树的中序遍历序列中每个节点的权值。

定义一棵子树的分数为左子树的分数

\times

右子树的分数

+

根节点的权值。

额外规定空树的分数为

1

，叶子的分数为该点的权值。

求一种满足该中序遍历的建树方案，使得整棵树的分数最大。

定义： $f(i,j)$ 表示中序遍历是 $w_{i\sim j}$ 的所有二叉树的得分的最大值。
状态转移方程： $f(i,j) = \max\{f(i,k-1) \times f(k+1,j) + w_k\}$ ，即将 $f_{i\ j}$ 表示的二叉树集合按根节点分类，则根节点在 $k$ 时的最大得分即为 $f(i,k-1) \times f(k+1,j) + w_k$ ，则 $f(i,j)$ 即为遍历 $k$ 所取到的最大值。
初始化： $f_{i\ i}=0$ 。
答案： $f_{1\ n}$ 。

在 DP 的过程中，一边 DP 一边记录最大分数的根节点。之后再递归输出先序遍历即可。

CPP

#include <bits/stdc++.h>
#define maxn 35
using namespace std;

int n, w[maxn], f[maxn][maxn], root[maxn][maxn];
void dfs(int l, int r) {
    if(l > r) return; //越界了，返回
    int k = root[l][r]; //根节点
    cout << k << " ";
    dfs(l, k - 1); //递归左子树
    dfs(k + 1, r); //递归右子树
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int l = n; l >= 1; l--) //枚举左端点
        for (int r = l; r <= n; r++) { //枚举右端点
            for (int k = l; k <= r; k++) { //枚举根节点
                int left = l == k ? 1 : f[l][k - 1]; //左子树
                int right = r == k ? 1 : f[k + 1][r]; //右子树
                int score = left * right + w[k]; //分数
                if(l == r) score = w[k]; //叶子节点
                if(f[l][r] < score) {
                    f[l][r] = score; //更新 DP
                    root[l][r] = k; //记录根节点
                }
            }
        }
    cout << f[1][n] << endl; //最后的答案
    dfs(1, n); //递归输出先序遍历
    return 0;
}

题解：P1040 [NOIP 2003 提高组] 加分二叉树

文章操作

相关推荐

评论

题解：P1040 [NOIP 2003 提高组] 加分二叉树