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

chrispang · 2025-03-01 21:22:58 · 题解

给定一个含有 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 一边记录最大分数的根节点。之后再递归输出先序遍历即可。

#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;
}