[NOIP 2003 提高组] 加分二叉树

形式化题目

给定长度为 $n$ 的正整数序列 $d_1, d_2, \dots, d_n$ 。要求构造一棵中序遍历恰好为 $(1, 2, \dots, n)$ 的二叉树，使得整棵树的加分最大。

对于任意子树 $T$ ：

若 $T$ 为空，其加分定义为 $1$ ；
若 $T$ 为非空，设其根节点编号为 $k$ （ $k \in \{1, \dots, n\}$ ），左子树为 $T_{\text{left}}$ ，右子树为 $T_{\text{right}}$ ，则加分为：
$\text{Score}(T) = \text{Score}(T_{\text{left}}) \times \text{Score}(T_{\text{right}}) + d_k$
若 $T$ 仅由单个叶节点 $k$ 构成，其加分为 $d_k$ 。

需要输出：

整棵树的最大加分；
取得最大加分的二叉树的前序遍历序列。

暴力解法

思路

因为整棵树的中序遍历固定为 $(1, 2, \dots, n)$ ，任意子树在中序遍历中必然对应一个连续区间 $[l, r]$ 。

对于当前区间 $[l, r]$ ，我们可以直接枚举该子树的根节点 $k$ （ $l \le k \le r$ ）。根据中序遍历的性质：

根节点 $k$ 的左子树对应中序区间 $[l, k - 1]$ ；
根节点 $k$ 的右子树对应中序区间 $[k + 1, r]$ 。

采用纯递归函数 solve(l, r)，枚举每个可能的根 $k$ ，递归计算左子树与右子树的最大得分与对应的前序遍历序列，然后按题目公式组合得分并取最大值。不使用记忆化或备忘录，直接遍历整棵状态划分树。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:21
 * update_at: 2026-10-23 23:21
 */
// brute.cpp：小数据暴力解。
// 通过递归枚举所有合法的二叉树形态（即每次在当前中序区间 [l, r] 中枚举根节点 k），
// 不使用记忆化，直接递归计算每种划分方式的得分并求最大值，同时记录最优根以输出前序遍历。
// 搜索状态数对应卡特兰数 C_n，复杂度随 n 呈指数爆炸，仅适合验证小规模数据（如 n <= 8）。
#include <iostream>
#include <vector>
using namespace std;

int n;
long long a[35];

struct Result {
    long long score;
    vector<int> preorder;
};

// 纯暴力递归搜索，不使用 memo / dp
Result solve(int l, int r) {
    if (l > r) {
        return {1, {}};
    }
    if (l == r) {
        return {a[l], {l}};
    }

    Result best = {-1, {}};
    for (int k = l; k <= r; ++k) {
        Result left_res = solve(l, k - 1);
        Result right_res = solve(k + 1, r);
        long long current_score = left_res.score * right_res.score + a[k];

        if (current_score > best.score) {
            best.score = current_score;
            best.preorder.clear();
            best.preorder.push_back(k);
            best.preorder.insert(best.preorder.end(), left_res.preorder.begin(), left_res.preorder.end());
            best.preorder.insert(best.preorder.end(), right_res.preorder.begin(), right_res.preorder.end());
        }
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    Result ans = solve(1, n);
    cout << ans.score << "\n";
    for (size_t i = 0; i < ans.preorder.size(); ++i) {
        cout << ans.preorder[i] << (i + 1 == ans.preorder.size() ? "" : " ");
    }
    cout << "\n";

    return 0;
}

复杂度

时间复杂度：每个大小为 $m$ 的区间都需要枚举根节点划分为两个更小的子区间，所有合法的二叉树形态数量等于卡特兰数 $C_n = \frac{1}{n+1}\binom{2n}{n} \approx \frac{4^n}{n^{1.5}\sqrt{\pi}}$ 。搜索过程中不记忆化，总递归调用次数与二叉树形态总数同阶，为指数级 $O(4^n / n^{1.5})$ 。当 $n$ 稍大时（如 $n \ge 15$ ）会彻底超时，仅适用于小数据（ $n \le 8$ ）。
空间复杂度：递归栈深度为 $O(n)$ ，每次返回包含前序遍历的数组，额外空间开销为 $O(n^2)$ 。

瓶颈

暴力的核心瓶颈在于重叠子问题的大量重复计算。不同全局树形结构中，相同的子区间 $[l, r]$ 会作为不同分支的子树被反复递归求解数千乃至数百万次。实际上，区间 $[l, r]$ 内部的最优子树形态及其最大得分，完全只取决于区间自身的端点 $l$ 和 $r$ ，与该子树在整棵树中的外部位置无关。因此，子问题总数实际上只有 $O(n^2)$ 个连续子区间。

正解

思路

1. 中序遍历与子区间的等价性

二叉树在中序遍历下的一个关键性质是：任意一棵子树所包含的所有节点，在中序遍历序列中必然对应一段连续的闭区间。

已知整棵树的中序遍历为 $(1, 2, \dots, n)$ ，因此：

任意子树都唯一对应一个区间 $[l, r]$ （ $1 \le l \le r \le n$ ）；
如果我们在子树区间 $[l, r]$ 中选定节点 $k$ （ $l \le k \le r$ ）作为该子树的根节点，根据中序遍历“先左子树、后根、再右子树”的顺序：
- 根节点 $k$ 的左子树对应中序区间 $[l, k - 1]$ ；
- 根节点 $k$ 的右子树对应中序区间 $[k + 1, r]$ 。

这一划分方式穷尽了在当前区间内构造二叉子树的所有可能。

2. 最优子结构与无后效性

子树 $[l, r]$ 的得分由左右子树的得分以及根节点权值 $d_k$ 共同决定。因为所有节点的分数均为正整数，所以每个非空区间的得分均为正数。由于乘法在正数域上的单调性，要最大化：

\text{Score}([l, r]) = \text{Score}([l, k - 1]) \times \text{Score}([k + 1, r]) + d_k

就必须使左右子区间的加分各自达到最大。子问题之间相互独立，局部最优可以递推至全局最优，满足无后效性，是经典的区间动态规划结构。

3. 状态定义与转移方程

定义 $dp[l][r]$ 表示以区间 $[l, r]$ 为中序遍历的所有可能二叉树中所能获得的最大加分。

枚举区间 $[l, r]$ 内的根节点 $k$ （ $l \le k \le r$ ），得到状态转移方程：

dp[l][r] = \max_{l \le k \le r} \Big( dp[l][k - 1] \times dp[k + 1][r] + d_k \Big)

下表列出样例序列 $[5,7,1,2,10]$ 的全部区间状态. 行表示左端点 $l$ , 列表示右端点 $r$ , 单元格是 $dp[l][r]$ ; 斜线下方为空区间, 不参与表格展示.

$l \backslash r$	1	2	3	4	5
1	5	12	13	25	145
2		7	8	15	85
3			1	3	13
4				2	12
5					10

例如 $dp[1][5]=145$ 的最优根是 $k=3$ : 左区间 $[1,2]$ 的最优值为 12, 右区间 $[4,5]$ 的最优值也为 12, 因此候选值是 $12\times12+d_3=12\times12+1=145$ . 表中的数值与 main.cpp 的区间 DP 一致.

4. 边界条件与初始化

空子树：根据题意，空子树加分为 $1$ 。即当 $l > r$ 时，规定 $dp[l][r] = 1$ 。通过这一设定，当根 $k = l$ （左子树为空）时， $dp[l][l - 1] \times dp[l + 1][r] + d_l = 1 \times dp[l + 1][r] + d_l$ ，与题目规则完美契合；右子树为空时同理。
叶子节点：当 $l = r$ 时，只有一个节点， $dp[l][l] = d_l$ 。

5. 记录最优决策与输出前序遍历

为了输出取得最大加分时的前序遍历（根 $\to$ 左子树 $\to$ 右子树）：

用辅助数组 $root[l][r]$ 记录在区间 $[l, r]$ 取得最大值时选取的根节点编号 $k$ ；
求解完成后，从全区间 $[1, n]$ 开始递归输出：
- 打印当前根 $k = root[l][r]$ ；
- 递归打印左子树 $[l, k - 1]$ ；
- 递归打印右子树 $[k + 1, r]$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:21
 * update_at: 2026-10-23 23:21
 */
#include <iostream>
#include <vector>
using namespace std;

// 节点数 <= 30，分数 <= 100，最大答案 <= 4e9，需要 long long
int n;
long long a[35];
long long dp[35][35];
int root[35][35];

// 递归打印前序遍历
void print_preorder(int l, int r) {
    if (l > r) return;
    int k = root[l][r];
    cout << k << " ";
    print_preorder(l, k - 1);
    print_preorder(k + 1, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // 初始化：空子树加分为 1
    for (int i = 1; i <= n + 1; ++i) {
        for (int j = 0; j <= n + 1; ++j) {
            if (i > j) dp[i][j] = 1;
        }
    }

    // 单个节点的加分就是其自身权值，根为其自身
    for (int i = 1; i <= n; ++i) {
        dp[i][i] = a[i];
        root[i][i] = i;
    }

    // 区间 DP：len 从 2 到 n
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = -1;
            for (int k = l; k <= r; ++k) {
                long long left_score = dp[l][k - 1];
                long long right_score = dp[k + 1][r];
                long long score = left_score * right_score + a[k];
                if (score > dp[l][r]) {
                    dp[l][r] = score;
                    root[l][r] = k;
                }
            }
        }
    }

    cout << dp[1][n] << "\n";
    print_preorder(1, n);
    cout << "\n";

    return 0;
}

复杂度

时间复杂度：
- 区间 DP 总状态数为 $O(n^2)$ 个区间 $[l, r]$ ；
- 每个区间转移需要枚举根节点 $k$ ，转移耗时为 $O(r - l + 1) = O(n)$ ；
- 动态规划总耗时为 $\sum_{\text{len}=1}^n (n - \text{len} + 1) \times \text{len} = O(n^3)$ ；
- 递归打印前序遍历每个节点仅访问一次，耗时 $O(n)$ ；
- 对于 $n < 30$ ， $n^3 \approx 2.7 \times 10^4$ ，执行时间在 $1\text{ ms}$ 以内。
空间复杂度：需要存储 $dp$ 矩阵与 $root$ 矩阵，空间复杂度为 $O(n^2)$ ，内存开销微乎其微。

总结

加分二叉树是二叉树中序遍历性质与区间 DP 的典范结合。解题的关键在于识别出：二叉树的中序子树与连续子区间具有一一对应关系。通过枚举区间的根节点，将一个大树划分为两个不相交的左、右子树区间，建立起清晰的区间包含关系；同时借助辅助数组记录最优决策点，便能轻松地在 DP 结束后递归重构出树的前序遍历。