企业官网建设流程全解析

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。要求输出：

1. tree \text{tree}tree的最高加分。

2. 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

输入 #1

5 5 7 1 2 10

输出 #1

145 3 1 2 4 5

说明/提示

数据规模与约定

对于全部的测试点，保证1 ≤ n < 30 1 \leq n< 301≤n<30，节点的分数是小于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 > ji>j时）。
  • 叶节点加分即自身分数，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 ] [k+1, j][k+1,j]，加分计算为：
  f [ i ] [ j ] = max ⁡ k = i j ( f [ i ] [ k − 1 ] × f [ k + 1 ] [ j ] + d k ) f[i][j] = \max_{k=i}^{j} \big( f[i][k-1] \times f[k+1][j] + d_k \big)f[i][j]=k=imaxj​(f[i][k−1]×f[k+1][j]+dk​)
  同时记录取得最大值的k kk作为根节点r t [ i ] [ j ] = k rt[i][j] = krt[i][j]=k。

2. 算法实现

1. 初始化：
   • 读入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]=1，r t [ i ] [ i ] = i rt[i][i] = irt[i][i]=i。
2. 区间 DP：
   • 按区间长度len从1 11到n − 1 n-1n−1枚举（len表示区间长度减1 11，即j = i + l e n j = i + lenj=i+len）。
   • 对于每个左端点i ii，计算右端点j = i + l e n j = i + lenj=i+len。
   • 初始令根为i ii，f [ i ] [ j ] = f [ i + 1 ] [ j ] + f [ i ] [ i ] f[i][j] = f[i+1][j] + f[i][i]f[i][j]=f[i+1][j]+f[i][i]（即左子树为空的情况），r t [ i ] [ j ] = i rt[i][j] = irt[i][j]=i。
   • 然后枚举根k kk从i + 1 i+1i+1到j − 1 j-1j−1，计算f [ i ] [ k − 1 ] × f [ k + 1 ] [ j ] + f [ k ] [ k ] f[i][k-1] \times f[k+1][j] + f[k][k]f[i][k−1]×f[k+1][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]。
3. 输出结果：
   • 最高加分为f [ 1 ] [ n ] f[1][n]f[1][n]。
   • 前序遍历：从根节点开始，递归输出根、左子树、右子树。定义函数print(l, r)：
     • 若l > r l > rl>r返回。
     • 输出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 < 30n<30，运算量极小，完全可行。
• 空间复杂度：需要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，输出最高加分和前序遍历。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll SZ=50;ll n;ll f[SZ][SZ],rt[SZ][SZ];voidprint(ll l,ll r){if(l>r)return;printf("%lld ",rt[l][r]);if(l==r)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 i=1;i<=n;i++){scanf("%lld",&f[i][i]);f[i][i-1]=1;rt[i][i]=i;}for(ll len=1;len<n;len++){for(ll i=1;i+len<=n;i++){ll j=i+len;f[i][j]=f[i+1][j]+f[i][i];rt[i][j]=i;for(ll k=i+1;k<j;k++){if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k]){f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];rt[i][j]=k;}}}}cout<<f[1][n]<<endl;print(1,n);return0;}