P1040 加分二叉树【洛谷算法习题】

P1040 加分二叉树网页链接P1040 加分二叉树题目描述设一个n nn个节点的二叉树tree \text{tree}tree的中序遍历为( 1 , 2 , 3 , … , n ) (1,2,3,\ldots,n)(1,2,3,…,n)其中数字1 , 2 , 3 , … , n 1,2,3,\ldots,n1,2,3,…,n为节点编号。每个节点都有一个分数均为正整数记第i ii个节点的分数为d i d_idi​tree \text{tree}tree及它的每个子树都有一个加分任一棵子树subtree \text{subtree}subtree也包含tree \text{tree}tree本身的加分计算方法如下subtree \text{subtree}subtree的左子树的加分× \times×subtree \text{subtree}subtree的右子树的加分 subtree \text{subtree}subtree的根的分数。若某个子树为空规定其加分为1 11叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为( 1 , 2 , 3 , … , n ) (1,2,3,\ldots,n)(1,2,3,…,n)且加分最高的二叉树tree \text{tree}tree。要求输出tree \text{tree}tree的最高加分。tree \text{tree}tree的前序遍历。输入格式第1 11行1 11个整数n nn为节点个数。第2 22行n nn个用空格隔开的整数为每个节点的分数。输出格式第1 11行1 11个整数为最高加分$ Ans \le 4,000,000,000$。第2 22行n nn个用空格隔开的整数为该树的前序遍历。如果你输出的前序遍历不合法可能会出现 UKE 的评测记录。输入输出样例 #1输入 #15 5 7 1 2 10输出 #1145 3 1 2 4 5说明/提示数据规模与约定对于全部的测试点保证1 ≤ n 30 1 \leq n 301≤n30节点的分数是小于100 100100的正整数答案不超过4 × 10 9 4 \times 10^94×109。解题思路本题是区间动态规划 二叉树遍历的经典问题。给定一棵二叉树的中序遍历为1 , 2 , … , n 1,2,\dots,n1,2,…,n每个节点有一个分数定义子树的加分为“左子树加分 × 右子树加分 根节点分数”空子树加分为1 11。要求找出加分最高的二叉树并输出最高加分及其前序遍历。由于中序遍历固定任意子树必然对应一个连续区间因此可以用区间 DP 求解。1. 问题等价转化中序遍历为1 ∼ n 1\sim n1∼n所以任何一棵子树都对应原序列的一个连续子区间[ i , j ] [i, j][i,j]。设f [ i ] [ j ] f[i][j]f[i][j]表示由区间[ i , j ] [i, j][i,j]构成的子树能获得的最大加分。设r t [ i ] [ j ] rt[i][j]rt[i][j]表示该最大加分对应的根节点编号用于最后输出前序遍历。边界条件空子树加分为1 11即f [ i ] [ i − 1 ] 1 f[i][i-1] 1f[i][i−1]1当i j i jij时。叶节点加分即自身分数f [ i ] [ i ] d i f[i][i] d_if[i][i]di​且r t [ i ] [ i ] i rt[i][i] irt[i][i]i。状态转移对于区间[ i , j ] [i, j][i,j]枚举根节点k ∈ [ i , j ] k \in [i, j]k∈[i,j]则左子树为[ i , k − 1 ] [i, k-1][i,k−1]右子树为[ k 1 , j ] [k1, j][k1,j]加分计算为f [ i ] [ j ] max ⁡ k i j ( f [ i ] [ k − 1 ] × f [ k 1 ] [ j ] d k ) f[i][j] \max_{ki}^{j} \big( f[i][k-1] \times f[k1][j] d_k \big)f[i][j]kimaxj​(f[i][k−1]×f[k1][j]dk​)同时记录取得最大值的k kk作为根节点r t [ i ] [ j ] k rt[i][j] krt[i][j]k。2. 算法实现初始化读入n nn和每个节点的分数d i d_idi​。对于所有i ii令f [ i ] [ i ] d i f[i][i] d_if[i][i]di​f [ i ] [ i − 1 ] 1 f[i][i-1] 1f[i][i−1]1r t [ i ] [ i ] i rt[i][i] irt[i][i]i。区间 DP按区间长度len从1 11到n − 1 n-1n−1枚举len表示区间长度减1 11即j i l e n j i lenjilen。对于每个左端点i ii计算右端点j i l e n j i lenjilen。初始令根为i iif [ i ] [ j ] f [ i 1 ] [ j ] f [ i ] [ i ] f[i][j] f[i1][j] f[i][i]f[i][j]f[i1][j]f[i][i]即左子树为空的情况r t [ i ] [ j ] i rt[i][j] irt[i][j]i。然后枚举根k kk从i 1 i1i1到j − 1 j-1j−1计算f [ i ] [ k − 1 ] × f [ k 1 ] [ j ] f [ k ] [ k ] f[i][k-1] \times f[k1][j] f[k][k]f[i][k−1]×f[k1][j]f[k][k]若大于当前f [ i ] [ j ] f[i][j]f[i][j]则更新f [ i ] [ j ] f[i][j]f[i][j]和r t [ i ] [ j ] rt[i][j]rt[i][j]。输出结果最高加分为f [ 1 ] [ n ] f[1][n]f[1][n]。前序遍历从根节点开始递归输出根、左子树、右子树。定义函数print(l, r)若l r l rlr返回。输出r t [ l ] [ r ] rt[l][r]rt[l][r]。递归print(l, rt[l][r] - 1)和print(rt[l][r] 1, r)。3. 复杂度分析时间复杂度状态数为O ( n 2 ) O(n^2)O(n2)每个状态枚举根节点O ( n ) O(n)O(n)总时间复杂度O ( n 3 ) O(n^3)O(n3)。n 30 n 30n30运算量极小完全可行。空间复杂度需要f ff和r t rtrt两个二维数组大小O ( n 2 ) O(n^2)O(n2)空间消耗很小。总结利用中序遍历固定为连续区间的性质将二叉树构造问题转化为区间 DP。通过枚举根节点划分左右子树递推计算最大加分并记录每个区间的根节点以便还原前序遍历。算法思路清晰实现简单适合小规模数据。代码简要说明全局数组f[50][50]存储区间最大加分rt[50][50]存储区间对应的根节点。初始化读入分数设置叶节点和空子树的加分初始化根节点。区间 DP外层循环区间长度内层循环左端点枚举根节点更新最大值和根位置。递归输出前序print(l, r)函数按照“根-左-右”的顺序输出节点编号。主函数读入数据调用 DP输出最高加分和前序遍历。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll SZ50;ll n;ll f[SZ][SZ],rt[SZ][SZ];voidprint(ll l,ll r){if(lr)return;printf(%lld ,rt[l][r]);if(lr)return;print(l,rt[l][r]-1);print(rt[l][r]1,r);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld,n);for(ll i1;in;i){scanf(%lld,f[i][i]);f[i][i-1]1;rt[i][i]i;}for(ll len1;lenn;len){for(ll i1;ilenn;i){ll jilen;f[i][j]f[i1][j]f[i][i];rt[i][j]i;for(ll ki1;kj;k){if(f[i][j]f[i][k-1]*f[k1][j]f[k][k]){f[i][j]f[i][k-1]*f[k1][j]f[k][k];rt[i][j]k;}}}}coutf[1][n]endl;print(1,n);return0;}