題目描述
設一個 $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～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