一、 题目分析在信息学奥赛的早期真题中NOIP 2003 的《加分二叉树》是一道具有代表性的好题。题面看似是在考查二叉树的构建与遍历但它却给出了一个很致命、也是破局核心的条件“二叉树的中序遍历为 (1, 2, 3, ..., n)”在数据结构中中序遍历的顺序是“左子树 → 根 → 右子树”。既然整棵树的中序遍历是连续的 1 到 n这就意味着一个物理定律对于树上的任意一棵子树它所包含的所有节点编号在物理上绝对构成一段连续的区间 [i,j]一旦清楚这一点这道题的图论外衣就被彻底扒下露出了它区间DP的真实面目。二、 核心状态定义与转移方程既然是处理连续区间我们直接套用区间DP的经典模型状态定义设 dp[i][j] 表示由编号i到j的节点所组成的子树能获得的最高加分。记号本状态溯源题目不仅要求最高分还要求输出前序遍历。我们额外开一个数组root[i][j]记录区间 [i,j] 取得最高分时是哪个节点k当了树根。转移策略枚举断点打擂台 对于区间 [i,j]我们不知道谁当根节点收益最大。因此我们让区间内的每一个节点 k (i≤k≤j) 都轮流“坐庄”当一次根节点。 当k为根时区间被完美切割左子树是 [i,k−1]右子树是 [k1,j]。根据题意“加分左子树加分×右子树加分根节点分数”得出状态转移方程dp[i][j]max(dp[i][j],dp[i][k−1]×dp[k1][j]a[k])三、 四个易错点区间DP的代码骨架很短但极其容易在初始化和边界上死循环。以下四个坑点都是校队同学真实出错的地方空子树的合法性越界陷阱当选定最左侧节点i当根时左子树区间变为 [i,i−1]。这是一个空树。题目规定空子树加分为 1。所以必须初始化 dp[i][i−1]1。注意当选定最右侧节点 n 当根时右子树变为 [n1,n]所以初始化的循环必须开到n1以防越界。叶子节点的独立性避免公式误伤题目规定“叶子的加分就是叶节点本身的分数”。如果我们让长度len1的区间也进入转移方程就会多乘上两个空子树的1导致分数计算错误。最稳妥的做法是手动初始化长度为1的区间dp[i][i]a[i]且root[i][i]i主循环从len2开始。右端点的当根权枚举根节点k时必须是for(int ki;kj; k)绝不能漏掉等号。二叉树允许只有左子树没有右子树的偏瘫形态最右边的节点 j 完全有资格当树根。整数溢出数据类型陷阱题目明确说明最高加分可能不超过 4×10^9。这个数值已经超过了32位有符号整型int的极限约 21.4 亿。因此dp数组必须果断开long long否则虽然信息学奥赛一本通能过但是实际上如果样例大一点是会出错的。四、 完整代码#include iostream using namespace std; int n; int a[35];//记录每个节点的原本分数 long long dp[35][35];//dp[i][j]代表i-j区间内最高加分 int root[35][35];//记录i和j区间取得最高分时的最优根节点 //输出前序遍历 void print(int l,int r){ if(lr) return;//遇到空节点就返回 int kroot[l][r];//否则就输出根 coutk ; print(l,k-1);//递归左子树 print(k1,r);//递归右子树 } int main(){ cinn; for(int i1;in;i) cina[i]; for(int i1;in1;i){//注意循环到n1防止右侧空子树越界 dp[i][i]a[i];//叶子结点的最高加分就是自己本身的分数 dp[i][i-1]1;//初始化空节点加分位1 root[i][i]i;//初始化每个节点是自己的根叶子节点当根的只能是它自己防止递归死循环 } for(int len2;lenn;len){//区间长度从2开始遍历 //枚举左端点 for(int i1;in-len1;i){ //右端点 int jilen-1; for(int ki;kj;k){//根节点 //状态转移如果l×ra大于之前加分就更新加分 //然后记录本次ij的最优根节点 if(dp[i][k-1]*dp[k1][j]a[k]dp[i][j]){ dp[i][j]dp[i][k-1]*dp[k1][j]a[k]; root[i][j]k; } } } } //输出最高加分 coutdp[1][n]endl; //递归输出先序遍历顺序 print(1,n); }