信息学奥赛算法练功房◌检测中
题单　·　习题解析

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

★★★ 「答案 ≤ 4×10⁹」超出 int（而上一页 P1063 那句 2.1×10⁹ 正好够）；★★★ 而最优前序不止一种 ⇒ 对拍不能逐字节比第二行 —— 多解轮数一个不差地等于「两个正确写法输出不同」的轮数

原题：洛谷 P1040出自 第 26 章 区间 DP：石子合并 的题单题面本地存档：2026-08-29
⚠ 先自己写一遍，再往下看

这一页不是标准答案，是一条阶梯：把大多数人真实会写出的第一版摆出来， 看它错在哪、慢在哪，再一步一步改。所以它对「已经自己动手撞过一次墙」的人最有用。
还没写过的话，先去写 —— 写出来的哪怕是错的，也比直接看这一页收获大。

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。 所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1040，日期见页头。两边不一致时信原站。

题目描述

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

subtree 的左子树的加分 × subtree 的右子树的加分 + subtree 的根的分数。

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

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

  1. tree 的最高加分。
  2. tree 的前序遍历。

输入格式

第 1 行 1 个整数 n，为节点个数。

第 2 行 n 个用空格隔开的整数，为每个节点的分数。

输出格式

第 1 行 1 个整数，为最高加分（Ans ≤ 4 000 000 000）。

第 2 行 n 个用空格隔开的整数，为该树的前序遍历。

如果你输出的前序遍历不合法，可能会出现 UKE 的评测记录。

说明/提示

对于全部的测试点，保证 1 ≤ n < 30，节点的分数是小于 100 的正整数，答案不超过 4 × 10⁹。

输入输出样例

输入

5
5 7 1 2 10

输出

145
3 1 2 4 5

根是 3：左子树 [1,2]（根 1，右孩子 2）加分 1 × 7 + 5 = 12， 右子树 [4,5]（根 4，右孩子 5）加分 1 × 10 + 2 = 12 ⇒ 总加分 12 × 12 + 1 = 145。

⚠⚠ 而这一组样例的最优前序遍历一共有 4 种（3 1 2 4 5 只是其中一种）—— 换一个同样正确的写法就会打出 3 2 1 5 4。这一页第 ④ 步整节在说这件事。

1★★ 关键的一步：中序是 1..n ⇒ 一棵子树就是一段连续区间

★ 断点在这道题叫「根」
    f[l][r] = max over k in [l, r] of ( f[l][k−1] × f[k+1][r] + d[k] )
                                          ↑ 左子树      ↑ 右子树     ↑ 根

和第 26 章正文完全一样的结构，只换了两处： 断点改名叫「根」，合并方式从「加」换成「乘再加」。

⚠ 而题面那两句话是两条规则，少读一条就差 1： 「若某个子树为空，规定其加分为 1」＋「叶子的加分就是叶节点本身的分数， 不考虑它的空子树」。 ⇒ 叶子是 d[i]，不是 1 × 1 + d[i]。 （写这一页的参照物时我就踩了这一下：n = 2 打成 13，正确答案是 12。）

p1040.cpp★ 这一版就能 AC
// P1040 [NOIP 2003 提高组] 加分二叉树 —— ★ 这一版就能 AC。
//
// ★★ 关键的一步：**中序遍历是 1..n ⇒ 一棵子树就是一段连续区间。**
//   选定这段区间的**根** k，左子树就是 [l, k-1]、右子树就是 [k+1, r] ——
//   这正是[第 26 章](/ch/26-interval-dp/)那个「枚举断点」的结构，只不过：
//     · 断点在这里叫「根」；
//     · 合并方式从「加」换成了「**左 × 右 + 根**」。
//
//       f[l][r] = max over k in [l, r] of ( f[l][k-1] × f[k+1][r] + d[k] )
//
// ⚠ 两处最容易漏：
//   ① **空子树的加分是 1，不是 0**（题面写死的）—— 写成 0 的话乘法直接把整棵子树归零；
//   ② **答案上界 4 × 10⁹ 超出了 `int`**（题面就写在输出格式里）⇒ 必须 `long long`。
//      ⚠ 顺带对照：同一章题单里的 [P1063](/sol/p1063/) 那句是 `E ≤ 2.1 × 10⁹`，
//      **正好在 int 里面**。两句话长得一样，一句够一句不够 —— 只能自己乘一遍。
//
// ★ 输出前序遍历：记下每段区间选的根 root[l][r]，再递归「根 → 左 → 右」。
//   ⚠ 最优方案**可能不止一种**（页面第 ④ 步量了这件事）——
//     所以这道题在洛谷上是带 SPJ 的，而**对拍不能逐字节比第二行**。


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


int n;
long long d[35], f[35][35];
int root[35][35];


int main() {
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    for (int i = 1; i <= n; i++) if (scanf("%lld", &d[i]) != 1) return 0;


    for (int l = 1; l <= n + 1; l++)
        for (int r = 0; r <= n; r++) f[l][r] = 1;        // ★ 空区间（l > r）加分记 1
    for (int i = 1; i <= n; i++) { f[i][i] = d[i]; root[i][i] = i; }


    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            long long best = -1;
            int bk = l;
            for (int k = l; k <= r; k++) {
                long long lv = (k == l) ? 1 : f[l][k - 1];
                long long rv = (k == r) ? 1 : f[k + 1][r];
                long long v = lv * rv + d[k];
                if (v > best) { best = v; bk = k; }       // 并列取最小的 k
            }
            f[l][r] = best;
            root[l][r] = bk;
        }


    printf("%lld\n", f[1][n]);
    // 前序遍历（根 → 左 → 右），末尾不留多余空格
    {
        vector<int> out;
        function<void(int, int)> go = [&](int l, int r) {
            if (l > r) return;
            out.push_back(root[l][r]);
            go(l, root[l][r] - 1);
            go(root[l][r] + 1, r);
        };
        go(1, n);
        for (size_t i = 0; i < out.size(); i++)
            printf("%d%c", out[i], i + 1 == out.size() ? '\n' : ' ');
    }
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

2★ 空子树记成 0 会怎样

DP 数组初值写 0 是最自然的动作 —— 而这里的合并是乘法，0 会把整棵子树归零。

p1040Zero.cpp✗ 空子树记 0
// ✗ P1040 的第一个坑：**空子树的加分记成了 0**。
//
// 题面写死的是「若某个子树为空，规定其加分为 **1**」。
// 而 DP 数组初值写 0 是最自然的动作 —— 于是每一次「左边或右边是空的」，
// 那一项乘法就把整棵子树的加分**归零**，只剩下根自己的分数。
//
// ★ 它算了什么能说死：**恒 ≤ 正解**（每个状态的取值都被压小了）。
//   页面上量过它被抓多少轮，以及官方样例挡不挡得住。


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


int n;
long long d[35], f[35][35];
int root[35][35];


int main() {
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    for (int i = 1; i <= n; i++) if (scanf("%lld", &d[i]) != 1) return 0;
    for (int i = 1; i <= n; i++) { f[i][i] = d[i]; root[i][i] = i; }


    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            long long best = -1;
            int bk = l;
            for (int k = l; k <= r; k++) {
                long long lv = (k == l) ? 0 : f[l][k - 1];      // ✗ 空子树记 0
                long long rv = (k == r) ? 0 : f[k + 1][r];      // ✗
                long long v = lv * rv + d[k];
                if (v > best) { best = v; bk = k; }
            }
            f[l][r] = best;
            root[l][r] = bk;
        }


    printf("%lld\n", f[1][n]);
    vector<int> out;
    function<void(int, int)> go = [&](int l, int r) {
        if (l > r) return;
        out.push_back(root[l][r]);
        go(l, root[l][r] - 1);
        go(root[l][r] + 1, r);
    };
    go(1, n);
    for (size_t i = 0; i < out.size(); i++)
        printf("%d%c", out[i], i + 1 == out.size() ? '\n' : ' ');
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
它 ≤ 正解 ★ 300 / 300
300 轮被抓 164
官方样例 ★ 挡住（122 vs 145）

3★★★ 「答案不超过 4 × 10⁹」——这一句和上一页那一句长得一样，结论正相反

★ 两句话摆在一起看
题 题面那句 int 上限 2 147 483 647 结论
P1063 能量项链 E ≤ 2.1 × 10⁹ 比它大 2.3% ★ int 刚好够
本题 Ans ≤ 4 × 10⁹ 是它的 1.86 倍 ★ int 不够，必须 long long

⇒ 同一章题单里的两道题，两句一模一样格式的「答案上界」，一句够一句不够。 ★★ 每一句「答案不超过 X」都得自己和 2147483647 比一遍，一次都不能省。

p1040Int.cpp（全程 int）✗ 顶格必挂
★★ 而「不信那句保证」的话，long long 也不够 —— 差得远

这一段全程用 __int128 算（⚠ 因为 long long 一溢出就是未定义行为， 那种数换台机器就变，不能写进正文）：
分数全取 99 时，答案第一次越过 int n = ★ 9
分数全取 99 时，答案第一次连 long long 都装不下 n = ★ 19
随机 n ≤ 29 的 300 轮里，真实答案越过题面那句保证 186 / 300（62%）
其中越过 int 190 / 300
其中连 long long 都装不下 ★ 64 / 300

⇒ ★★★ 题面那句 Ans ≤ 4 × 10⁹ 挡掉的不是「int 不够」，是「连 long long 都不够」的那一大类输入。 ⇒ 而对我们的生成器来说，这就是第 19 章 P1090 那条的又一次现场： 自己造数据时要连「输出侧的保证」一起满足，否则测的是题目不会给的输入。 ★ 本页对拍用的默认档是 n ≤ 8（分数 ≤ 99），刚好落在「连 int 都还没越过」的那一侧。

4★★★ 这道题的对拍不能逐字节比 —— 因为最优方案不止一种

下面这一版是对的：它只是在并列时取最大的那个根（正解取的是最小的）。

p1040Last.cpp（同样正确的另一种写法）★ 第一行永远一样，第二行未必
// P1040：**同样正确**的另一版 —— 并列时取**最大**的那个根（正解取的是最小的）。
//
// ★★★ 它存在的意义不是「演示一个错误」，恰恰相反：**它是对的**。
//   最高加分那一行永远和正解一模一样，可**第二行（前序遍历）在有多个最优解时不同**。
//
// ⇒ 这就是这一页最值钱的一件事：**这道题的对拍不能逐字节比。**
//   页面上量过：随机 300 轮里，两版第二行不同的轮数 ≡ 「最优方案不止一种」的轮数。
//   （洛谷上这道题是带 SPJ 的，题面还专门提醒「如果你输出的前序遍历不合法，
//     可能会出现 UKE 的评测记录」。）
//
// ⚠ 和[第 19 章 P2240](/sol/p2240/) 那条凑成一对：那里是**实数**不能逐字节比，
//   这里是**答案不唯一**不能逐字节比 —— 两种情形，同一条规矩。


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


int n;
long long d[35], f[35][35];
int root[35][35];


int main() {
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    for (int i = 1; i <= n; i++) if (scanf("%lld", &d[i]) != 1) return 0;
    for (int l = 1; l <= n + 1; l++)
        for (int r = 0; r <= n; r++) f[l][r] = 1;
    for (int i = 1; i <= n; i++) { f[i][i] = d[i]; root[i][i] = i; }


    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            long long best = -1;
            int bk = l;
            for (int k = l; k <= r; k++) {
                long long lv = (k == l) ? 1 : f[l][k - 1];
                long long rv = (k == r) ? 1 : f[k + 1][r];
                long long v = lv * rv + d[k];
                if (v >= best) { best = v; bk = k; }      // ★ 并列取**最大**的 k
            }
            f[l][r] = best;
            root[l][r] = bk;
        }


    printf("%lld\n", f[1][n]);
    vector<int> out;
    function<void(int, int)> go = [&](int l, int r) {
        if (l > r) return;
        out.push_back(root[l][r]);
        go(l, root[l][r] - 1);
        go(root[l][r] + 1, r);
    };
    go(1, n);
    for (size_t i = 0; i < out.size(); i++)
        printf("%d%c", out[i], i + 1 == out.size() ? '\n' : ' ');
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

官方样例上它打出 145 和 3 2 1 5 4 —— 加分一模一样，前序遍历和样例给的不同。

★★ 量一遍：多解到底有多常见（各 300 轮，n ≤ 8）
分数值域 1~3 1~20 1~99（题面顶格）
最优前序不止一种的轮数 244 174 164
两个正确写法第二行不同的轮数 ★ 244 ★ 174 ★ 164
两个正确写法第一行不同的轮数 0 0 0

★★★ 前两行一个不差（三档全中）—— 这不是巧合，是等价： 只要最优方案不止一种，两种取法就可能给出不同的前序。 ⇒ 又一次「触发条件 ≡ 抓获数」，而这一次「被抓」的是一个完全正确的程序。

⇒ ★★★ 所以这道题的对拍必须这么写： 第一行（最高加分）逐字节比；第二行只能拿去验 —— 验它是不是一棵合法的、中序为 1..n 且加分等于第一行的树的前序。 （洛谷上这道题正是带 SPJ 的，题面还专门提醒「输出的前序遍历不合法可能会 UKE」。）

⚠ 和第 19 章 P2240 凑成一对：那里是实数不能逐字节比， 这里是答案不唯一不能逐字节比。两种情形，同一条规矩。

5★ 规模

n < 30 ⇒ 区间数 × 每段枚举的根 = 4 495 次转移。这道题的规模小到可以忽略 —— 它考的全是「状态怎么定」「边界怎么读」「输出怎么比」。

6度量程序、生成器和参照物

p1040Count.cpp度量程序（本页所有数字都出自它）
p1040Gen.cpp数据生成器
p1040Brute.cpp参照物：把所有树形建一遍，按题面定义算分

7一页纸
★★ 关键的一步 中序是 1..n ⇒ 一棵子树就是一段连续区间，断点改名叫「根」，合并从「加」换成「乘再加」
⚠ 边界那两句话 「空子树记 1」＋「叶子不考虑它的空子树」是两条规则（我写参照物时踩过）
空子树记 0 恒 ≤ 正解（300/300），被抓 164；样例挡住
★★★ 「答案 ≤ 4 × 10⁹」 超出 int 1.86 倍 ⇒ 必须 long long；而上一页 P1063 那句 2.1 × 10⁹ 正好够
★★ 不信那句保证呢 全 99 时 n = 9 越过 int、n = 19 连 long long 都不够；随机顶格 64/300 越过 long long
★★★ 对拍不能逐字节比 最优前序不止一种（顶格 164/300）—— 而「两个正确写法第二行不同」的轮数一个不差地等于它
规模 n < 30 ⇒ 4 495 次转移，小到可以忽略