C区间 DP

加分二叉树型

枚举根·区间即子树

本课摘要

加分二叉树型课程回答“枚举区间根节点时，子区间如何对应左右子树”。内容以枚举根·区间即子树为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断加分二叉树型的适用条件与状态边界
  • 围绕“枚举根·区间即子树”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

加分二叉树：中序固定，怎么建最划算

换一个和石子合并神似、却长着「树」外壳的问题。给 5 个节点，分数依次是 5, 7, 1, 2, 105,\ 7,\ 1,\ 2,\ 10。 要把它们建成一棵二叉树，唯一约束是：中序遍历必须恰好是 1,2,3,4,51,2,3,4,5（即节点编号 = 它在中序里的位置）。一棵子树的加分这样算——记左子树加分 LL、右子树加分 RR、根分数 ss：

scoretree=L×R+s\text{score}_{\text{tree}}=L\times R+s

并约定空子树的加分为 11（乘法里的单位元，不改变乘积）。不同的建树方式，总加分不同——问整棵树能拿到的最大加分，还要输出这棵最优树的前序遍历。

节点 15节点 27节点 31节点 42节点 510中序遍历固定为 1 … 5（左根右）选它作根左半 → 左子树右半 → 右子树
中序固定为 1…5。任选一个节点当根（图中选了节点 3）——它左边的节点全落进左子树、右边的全落进右子树。这就是「枚举根」。

为什么这题绕不开区间？关键在中序被钉死了。二叉树的中序是「左 → 根 → 右」，所以一旦某个节点 kk 当了根，中序里排在它前面的节点必然全在左子树、排在它后面的全在右子树——绝不会交叉。于是「以 kk 为根」就把连续的一段编号 [i,j][i,j] 干净地劈成两段 [i,k−1][i,k-1] 与 [k+1,j][k+1,j]，各自又是一棵更小的子树。

中序序列上一段连续区间12345区间 [2, 4]⇕就是这一棵子树[2,4] 的一种二叉子树324左右
一段连续区间 [i,j] ↔ 一棵子树：钦定根 k 后，[i,k−1] 成左子树、[k+1,j] 成右子树——区间的「劈分」正是树的「拆解」，这就是「区间即子树」。

要枚举所有合法二叉树？其数量是卡特兰数，随 nn 指数爆炸，不可行。但上面那句「一段连续区间恰好是一棵子树」已经把出路点明——这正是区间 DP 的入口，和石子合并同一个模子。

状态与转移：枚举根，左右子树相乘

定状态。设 dp[i][j]dp[i][j] 表示：把中序编号 ii 到 jj 这段连续区间建成一棵子树能拿到的最大加分。 要把 [i,j][i,j] 建成子树，必须先钦定它的根——设根是 kk（i≤k≤ji\le k\le j），则左子树是区间 [i,k−1][i,k-1]、右子树是 [k+1,j][k+1,j]，两者都是更短的、已解的子区间。

区间 [i, j] 建成一棵子树dp[i][j] = ?枚举根 k：左半 [i,k−1] 作左子树，右半 [k+1,j] 作右子树左子树 [i, k−1] 的最大加分dp[i][k−1]（空则记 1）右子树 [k+1, j] 的最大加分dp[k+1][j]（空则记 1）dp[i][k−1] × dp[k+1][j] + score[k]
dp[i][j] 枚举根 k：左子树取 dp[i][k−1]、右子树取 dp[k+1][j]（任一为空则记 1），二者相乘再加上根分数 score[k]。

按加分定义，以 kk 为根时这棵子树的加分是 dp[i][k−1]×dp[k+1][j]+score[k]dp[i][k-1]\times dp[k+1][j]+\mathrm{score}[k]。哪个根最好？把每个 kk 都试一遍，取最大：

dp[i][j]=max⁡i≤k≤j(dp[i][k−1]×dp[k+1][j])+score[k]dp[i][j]=\max_{i\le k\le j}\big(dp[i][k-1]\times dp[k+1][j]\big)+\mathrm{score}[k]

这里 i>ji>j 的空区间（当 k=ik=i 时左子树 [i,i−1][i,i-1] 就是空、k=jk=j 时右子树为空）约定 dp=1dp=1：空子树没有节点，乘上 11 不改变乘积。 边界：dp[i][i]=score[i]dp[i][i]=\mathrm{score}[i]（单节点自成一棵子树）。答案：dp[1][n]dp[1][n]。

和石子合并一样，dp[i][j]dp[i][j] 依赖的都是更短的子区间，所以递推必须按区间长度由短到长——短子树先算好，长区间枚举根时才有得引用。

本质：区间就是子树，分割点就是根

区间 DP 的同一套骨架，在这里换了层皮：石子合并枚举分割点把区间拆成左右两段相加；加分二叉树枚举根把区间拆成左右两棵子树相乘再加根分。一句话对上号——「一段连续区间 ⇔ 一棵子树；区间里选的那个分割点/根 ⇔ 子树的根」。认出这层对应，就把「建树」这件看似要枚举卡特兰数棵树的事，压成了 O(n2)O(n^2) 张三角表格、每格 O(n)O(n) 枚举根。

跟着算一遍

用开头的例子（分数 score=[5,7,1,2,10]\mathrm{score}=[5,7,1,2,10]，中序编号 1..51..5）走几步，重点盯住长度由短到长、以及空子树记 1：

0
对角线（长度 1）。 每个节点自成一棵子树：dp[i][i]=score[i]dp[i][i]=\mathrm{score}[i]，即 5,7,1,2,105,7,1,2,10。这是三角表的地基。
1
长度 2，看 [1,2][1,2]（分数 5,75,7）：根取 11 → 左空 11、右 dp[2][2]=7dp[2][2]=7，加分 1×7+5=121\times7+5=12；根取 22 → 左 55、右空 11，5×1+7=125\times1+7=12。两者都 1212，取 dp[1][2]=12dp[1][2]=12。
2
长度 3，看 [1,3][1,3]（分数 5,7,15,7,1，已知 dp[2][3]=8dp[2][3]=8）：根 11 → 1×dp[2][3]+5=1×8+5=131\times dp[2][3]+5=1\times8+5=13；根 22 → dp[1][1]×dp[3][3]+7=5×1+7=12dp[1][1]\times dp[3][3]+7=5\times1+7=12；根 33 → dp[1][2]×1+1=12×1+1=13dp[1][2]\times1+1=12\times1+1=13。最大是 dp[1][3]=13dp[1][3]=13；根 11 与根 33 打平，按字典序最小取根 = 节点 1（详见后文坑）。
3
长度 5，整段 [1,5][1,5]：逐个试根，根 = 节点 33 时 dp[1][2]×dp[4][5]+1=12×12+1=145dp[1][2]\times dp[4][5]+1=12\times12+1=145 胜出——dp[1][5]=145dp[1][5]=145，正是最大加分。别被「节点 3 分数只有 1」骗到：乘法结构让它当根反而把左右两个 1212 撑成了 144144。
下面的演示把三角表按长度一层层填满，高亮每个 dp[i][j]dp[i][j] 选中的根 kk 及左右子树来源。改改分数，看最优根如何随之跳动。

看三角表一层一层长出来 · 枚举根、左右相乘

节点按中序排开（可改每个分数 · 3～5 个节点）
1
分数 score
5
2
分数 score
7
3
分数 score
1
4
分数 score
2
5
分数 score
10
j=1
j=2
j=3
j=4
j=5
i=1
i=2
i=3
i=4
i=5
5
·
·
·
·
·
7
·
·
·
·
·
1
·
·
·
·
·
2
·
·
·
·
·
10
当前计算 依赖来源 被选转移 已确定
dp[i][i]=score[i]dp[i][i]=\mathrm{score}[i]
对角线（区间长度 1）：单个节点自成一棵子树，dp[i][i]=score[i]；空子树加分约定为 1。
已暂停，第 1 步，共 12 步，1 倍速

表是个上三角（只有 i≤ji\le j 才是合法区间）。填表外层枚举长度 len=2…n\mathrm{len}=2\ldots n、内层枚举左端点 ii、最内枚举根 kk——三层循环、外层是长度，和几乎所有区间 DP 一个骨架。约 O(n2)O(n^2) 个区间、每个枚举 O(n)O(n) 个根，总复杂度 O(n3)O(n^3)。加分二叉树的 n≤30n\le 30，轻松通过。中文伪代码：

for 长度 len = 2 … n:            // ★外层枚举区间长度，由短到长
  for 左端点 i = 1 … n-len+1:
    j = i + len - 1
    for 根 k = i … j:            // 枚举区间 [i,j] 的根
      左 = (k>i) ? dp[i][k-1] : 1   // 空子树记 1
      右 = (k<j) ? dp[k+1][j] : 1
      若 左*右 + score[k] 更大:
        dp[i][j] = 左*右 + score[k]
        root[i][j] = k           // 记下根，供前序回溯

深化：从 root 表前序回溯出整棵树

光有最大加分还不够，本题第二问要输出最优树的前序遍历。诀窍是在填表时顺手记下每个区间选的根：转移取到最优的那个 kk，存进 root[i][j]\mathrm{root}[i][j]。等整张表填完，从整区间 [1,n][1,n] 出发递归就能把树还原——先输出根、再递归左子树、再递归右子树：

pre(i,j): k=root[i][j]; emit k; pre(i,k−1); pre(k+1,j)\mathrm{pre}(i,j):\ k=\mathrm{root}[i][j];\ \text{emit }k;\ \mathrm{pre}(i,k-1);\ \mathrm{pre}(k+1,j)

先输出根 kk、再递归左子树 [i,k−1][i,k-1]、再递归右子树 [k+1,j][k+1,j]——这正是前序遍历（根 → 左 → 右）的定义。空区间 i>ji>j 直接返回、什么都不输出。 这套「记录决策 + 回溯还原方案」和石子合并枚举分割点是同一路数：石子那里若要还原合并顺序，也照样存 root[l][r]=root[l][r]= 最优分割点、再递归左右段。区别仅在——加分树记的是根、还原出的是树结构；石子记的是分割点、还原出的是合并树。

下面把 root[i][j]root[i][j] 前序回溯出的最优树画出来。点任意节点，看它这棵子树对应中序上哪一段连续区间——「区间即子树」一目了然。

建树演示：区间 ⇔ 子树

节点按中序排开（与上一个演示同一组分数 · 3～5 个）
1
分数 score
5
2
分数 score
7
3
分数 score
1
4
分数 score
2
5
分数 score
10
点任意节点 → 高亮它这棵子树，并在下方中序刻度条上点亮它对应的连续区间。 整棵树最大加分 145，前序遍历 3 1 2 4 5。
右右左右2715510423112345中序序列（固定 1…5）
点一个节点看它对应的连续区间。整棵树 = 区间 [1, 5]，其根 = 节点 3（前序第一个）。

两个常见坑：空子树的 1，和相等时记哪个根

其一，空子树加分是 11 不是 00——它进的是乘法，记 0 会把整棵子树的加分抹成 0。写代码时用「越界即取 1」处理端点根（k=ik=i 或 k=jk=j）。 其二，本题前序遍历不唯一时要求字典序最小：枚举 kk 从小到大、且转移用严格大于 >> 才更新，就能让相等时保留更小的根——更小的根当前序第一个，字典序自然更小。

例题

P1040[NOIP2003 提高组] 加分二叉树NOIP2003 提高组普及+/提高
题意
nn 个节点中序为 1..n1..n，各带分数。子树加分 = 左子树加分 ×\times 右子树加分 ++ 根分数，空树记 11。求整棵树最大加分，并输出最优树的前序遍历（多解取字典序最小）。
为什么选它（本类型黄金范例）
它是「枚举根区间 DP」最纯正的范本，且把方案回溯逼到台前：不仅要 dp[1][n]dp[1][n]，还要还原整棵树——必须在转移时记 root[i][j]root[i][j]、事后前序递归。一题吃透「区间即子树 + 记录决策回溯」两件事。
转移 · 复杂度
dp[i][j]=max⁡k(dp[i][k−1]⋅dp[k+1][j])+score[k]dp[i][j]=\max_k(dp[i][k-1]\cdot dp[k+1][j])+\mathrm{score}[k]，空区间记 11；外层长度、内层左端点、最内根；时间 O(n3)O(n^3)，n≤30n\le 30。分数乘积可能很大，用 long long\texttt{long long}。
参考代码（含前序回溯 · ShanireZ 风）
C++
在洛谷打开 P1040 
#include <iostream>
using namespace std;

const int N = 35;
int n;
long long score[N];              // 每个节点的分数（按中序 1..n 排）
long long dp[N][N];              // dp[i][j] = 区间[i,j]建成一棵子树的最大加分
int root[N][N];                  // root[i][j] = 取到最优时选的根，供前序回溯

// 前序遍历输出最优树：根 → 左子树 → 右子树
void preorder(int i, int j)
{
    if (i > j) return;           // 空子树，什么都不输出
    int k = root[i][j];          // 这段区间的最优根
    cout << k << " ";
    preorder(i, k - 1);          // 左子树 = 区间左半
    preorder(k + 1, j);          // 右子树 = 区间右半
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> score[i];

    for (int i = 1; i <= n; i++) // 区间长度 1：单节点自成子树
    {
        dp[i][i] = score[i];
        root[i][i] = i;
    }

    for (int len = 2; len <= n; len++)              // ★外层枚举区间长度，由短到长
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            for (int k = i; k <= j; k++)            // 枚举根 k
            {
                // 空子树（k 在端点）的加分记 1：越界即视作 1
                long long lft = (k - 1 >= i) ? dp[i][k - 1] : 1;
                long long rgt = (k + 1 <= j) ? dp[k + 1][j] : 1;
                long long cur = lft * rgt + score[k];
                if (cur > dp[i][j])                 // 取最大，并记下根（相等取更小 k：不覆盖即最小）
                {
                    dp[i][j] = cur;
                    root[i][j] = k;
                }
            }
        }

    cout << dp[1][n] << endl;    // 第一问：最大加分
    preorder(1, n);              // 第二问：最优树的前序遍历
    cout << endl;
    return 0;
}
P1880[NOI1995] 石子合并NOI1995提高+/省选-
题意
nn 堆石子摆成一环，每次合并相邻两堆、代价为两堆之和，直到并成一堆。分别求最小与最大总代价。
为什么放这里（同构对照）
拿它和加分二叉树并置，是为了看清两者是同一个区间 DP：石子枚举分割点 kk、把 [l,r][l,r] 拆成 [l,k][l,k] 与 [k+1,r][k+1,r] 两段相加再补区间和；加分树枚举根 kk、把 [i,j][i,j] 拆成 [i,k−1][i,k-1] 与 [k+1,j][k+1,j] 两棵子树相乘再补根分。枚举根 ↔ 枚举分割点，一层皮之隔。
转移 · 复杂度
f/g[l][r]=opt(f/g[l][k]+f/g[k+1][r])+sum(l,r)f/g[l][r]=\mathrm{opt}(f/g[l][k]+f/g[k+1][r])+\mathrm{sum}(l,r)；断环为链（复制一倍成 2n2n）后取所有长度 nn 的窗口；时间 O(n3)O(n^3)。详见 石子合并（链形）一节。
参考代码（断环为链 · 双问并行）
C++
在洛谷打开 P1880 
#include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;
int n;
int a[205];                      // 断环为链：复制一倍成 2n
int pre[205];                    // 前缀和，sum(l..r) = pre[r] - pre[l-1]
int f[205][205];                 // 最小合并代价
int g[205][205];                 // 最大合并代价

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i];         // 复制一倍
    }
    for (int i = 1; i <= 2 * n; i++)
        pre[i] = pre[i - 1] + a[i];

    for (int len = 2; len <= n; len++)              // 长度只到 n（一圈）
        for (int l = 1; l + len - 1 <= 2 * n; l++)
        {
            int r = l + len - 1;
            int s = pre[r] - pre[l - 1];            // 本区间合并代价 = 区间和
            f[l][r] = INF;
            g[l][r] = -INF;
            for (int k = l; k <= r - 1; k++)        // ★枚举分割点 k（对照：加分树枚举根）
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s);
                g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s);
            }
        }

    int mn = INF, mx = -INF;
    for (int l = 1; l <= n; l++)                    // 枚举起点，取所有长度为 n 的窗口
    {
        mn = min(mn, f[l][l + n - 1]);
        mx = max(mx, g[l][l + n - 1]);
    }
    cout << mn << endl << mx << endl;
    return 0;
}

练习

P1436棋盘分割二维区间递归分割：把棋盘沿横或竖线切成两块，递归下去，求分割成 n 块后各块总分平方和的最小值。状态 dp[次数][x1][y1][x2][y2] 记子矩形，转移枚举每条横/竖切割线——是「枚举分割点」在二维矩形上的推广，记忆化搜索最省事。在洛谷打开
P1043[NOIP2003 普及组] 数字游戏环形 + 区间划分 DP：数字排成环，切成 m 段求各段和取模再相乘的最大/最小。断环为链后，dp[l][r][k] 记「区间 [l,r] 分成 k 段」的最优，转移枚举最后一段的分割点。取模后可能为负，求最小值时别漏「负负得正」。与加分树同为『区间上枚举一个分界并合并』的区间 DP。在洛谷打开

小字说明：洛谷上与「加分二叉树」完全同型（中序固定 + 枚举根 + 乘法加分 + 前序回溯）的原生题目较少，P1040 本身即该型的代表与压卷题。上面两题都是更广义的「区间上枚举分界」区间 DP——一个把分割推到二维矩形、一个叠加「分成 k 段」的维度，用来巩固「枚举分割/根 + 按区间递推」的通用手感，而非同题换皮。

想亲手感受「同一批分数、换个根，总加分差多少」？到 C 部分页的互动里挑一棵树，再对照 DP 给出的最优。

已进入 加分二叉树型 · 区间 DP · DP大师