题目描述
设一个 $n$ 个节点的二叉树 $\text{tree}$ 的中序遍历为$(1,2,3,\dots ,n)$，每个节点都有一个分数（均为正整数）。任一棵子树 $\text{subtree}$（包含 $\text{tree}$ 本身）的加分计算方法如下：

$\text{subtree}$ 的左子树的加分 $\times$ $\text{subtree}$ 的右子树的加分 $+$ $\text{subtree}$ 的根的分数

若某个子树为空，规定其加分为 $1$

叶子的加分就是叶节点本身的分数

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

$\text{tree}$ 的最高加分

$\text{tree}$ 的前序遍历

输入格式

第 $1$ 行：整数 $n$（节点数）

第 $2$ 行：$n$ 个空格分隔的整数（节点分数）

输出格式

第 $1$ 行：最高加分

第 $2$ 行：二叉树的前序遍历序列（空格分隔）

数据范围
$1\le n<30$，节点分数是小于 $100$ 的正整数，答案不超过 $4\times 10^9$

解题思路
算法分析：区间动态规划
本题需要构造一棵中序遍历为 $1\sim n$ 的二叉树，使得其加分最大。由于中序遍历的特性（左子树-根-右子树），我们可以使用区间动态规划来解决：

状态定义：

dp[l][r]：表示节点编号在区间 $[l,r]$ 内构成的子树的最大加分

root[l][r]：表示区间 $[l,r]$ 构成最大加分子树的根节点编号

状态转移：

枚举区间 $[l,r]$ 中的每个节点 $k$ 作为根节点

计算以 $k$ 为根时的加分：

若 $k=l$（无左子树）：加分 = 右子树加分 + 根节点分数

若 $k=r$（无右子树）：加分 = 左子树加分 + 根节点分数

否则：加分 = 左子树加分 × 右子树加分 + 根节点分数

更新区间 $[l,r]$ 的最大加分和对应的根节点

前序遍历输出：

使用递归方法输出：根节点 → 左子树 → 右子树

根据记录的 root 数组确定每个子树的根节点

复杂度分析
时间复杂度：$O(n^3)$
三重循环：枚举区间长度($n$)、区间起点($n$)、根节点位置($n$)

空间复杂度：$O(n^2)$
存储二维DP数组和根节点记录数组

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int n,dp[N][N],tree[N][N];
int qiu(int l,int k,int r)
{if(k==l)return dp[k+1][r]+dp[k][k];if(r==k)return dp[l][k-1]+dp[k][k];return dp[l][k-1]*dp[k+1][r]+dp[k][k];
}
void shuchu(int l,int r)
{if(r<l)return;cout<<tree[l][r]<<" ";shuchu(l,tree[l][r]-1);shuchu(tree[l][r]+1,r);
}
int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>dp[i][i];tree[i][i]=i;}for(int i=2;i<=n;i++)for(int j=1;j<=n-i+1;j++){int jj=j+i-1;for(int r=j;r<=jj;r++)if(qiu(j,r,jj)>dp[j][jj]){tree[j][jj]=r;dp[j][jj]=qiu(j,r,jj);}}cout<<dp[1][n]<<'\n';shuchu(1,n);
//	cout<<tree[1][2];return 0;
}

外层循环：枚举区间长度（从2到n）

中层循环：枚举区间起点（保证区间在[1,n]内）

内层循环：枚举可能的根节点位置

计算当前根节点的加分并更新最大值和根节点记录

3. 前序遍历输出

void shuchu(int l, int r) {if (l > r) return;cout << tree[l][r] << " ";shuchu(l, tree[l][r] - 1);shuchu(tree[l][r] + 1, r);
}

递归输出前序遍历序列

输出顺序：当前根节点 → 左子树区间 → 右子树区间

递归终止条件：区间为空（l > r）

4. 边界处理函数

int qiu(int l, int k, int r) {if (k == l) // 左子树为空return dp[k][k] + dp[k+1][r];if (k == r) // 右子树为空return dp[k][k] + dp[l][k-1];return dp[k][k] + dp[l][k-1] * dp[k+1][r];
}

处理根节点在区间端点的特殊情况

当根节点在左端点时，左子树为空（加分为1）

当根节点在右端点时，右子树为空（加分为1）

示例分析
输入：

5
5 7 1 2 10

输出：

145
3 1 2 4 5

解释：
最高加分145对应的二叉树结构：

    3/ \1   4\   \2   5
前序遍历：3 → 1 → 2 → 4 → 5

加分计算：

叶子节点加分：节点2(2分)、节点5(10分)

子树[1,2]：左空(1) × 右节点2(2) + 根节点1(7) = 1×2+7=9

子树[4,5]：左节点4(1) × 右节点5(10) + 根节点4(1) = 1×10+1=11

整棵树：左子树1,2 × 右子树4,5 + 根节点3(5) = 9×11+5=104