題目鏈接

[NOIP2003 提高組] 加分二叉樹

題目描述

設一個 $n$ 個節點的二叉樹 $\text{tree}$ 的中序遍歷為$(1,2,3,\dots ,n)$，其中數字 $1,2,3,\dots ,n$ 為節點編號。每個節點都有一個分數（均為正整數），記第 $i$ 個節點的分數為 $d_i$，$\text{tree}$ 及它的每個子樹都有一個加分，任一棵子樹 $\text{subtree}$（也包含 $\text{tree}$ 本身）的加分計算方法如下：

$\text{subtree}$ 的左子樹的加分 $\times$ $\text{subtree}$ 的右子樹的加分 $+$ $\text{subtree}$ 的根的分數。

若某個子樹為空，規定其加分為 $1$，葉子的加分就是葉節點本身的分數。不考慮它的空子樹。

試求一棵符合中序遍歷為 $(1,2,3,\dots ,n)$ 且加分最高的二叉樹 $\text{tree}$。要求輸出

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

2. $\text{tree}$ 的前序遍歷。

輸入格式

第 $1$ 行 $1$ 個整數 $n$，為節點個數。

第 $2$ 行 $n$ 個用空格隔開的整數，為每個節點的分數

輸出格式

第 $1$ 行 $1$ 個整數，為最高加分（$Ans\le 4,000,000,000$）。

第 $2$ 行 $n$ 個用空格隔開的整數，為該樹的前序遍歷。

樣例 #1

樣例輸入 #1

5
5 7 1 2 10

樣例輸出 #1

145
3 1 2 4 5

提示

數據規模與約定

對于全部的測試點，保證 $1\le n<30$，節點的分數是小于 $100$ 的正整數，答案不超過 $4\times 10^9$。

算法思想

最高加分

根據題目描述：

• 一棵二叉樹的中序遍歷為$(1,2,3,\dots ,n)$。

在中序遍歷中，一旦確定了根結點，那么左右子樹的節點編號一定在根結點兩側，例如當根節點為$3$時，那么左子樹的結點編號為$1,2$，右子樹的結點編號為$4,5,\dots ,n$，如下圖所示：

• 加分計算方法為左子樹的加分 $\times$ 右子樹的加分 $+$根的分數。

求一棵符合中序遍歷為 $(1,2,3,\dots ,n)$ 且加分最高的二叉樹，就是求以根節點為中心，將左右兩個區間（子樹）合并在一起的最大值，因此可以使用區間型動態規劃進行處理。

狀態表示

$f[i,j]$表示二叉樹中序遍歷的節點編號在區間$[i,j]$的最大加分分值。

狀態計算

從最后一個合并位置，也就是根節點的位置可以將狀態計算分為下面幾種情況：

• 根節點在$i$位置，此時左子樹為空，加分為$1\times$，得到的分數為$1\times f[i+1][j]+w[i]$。
• 根節點在$i+1$位置，得到的分數為$f[i][i]\times f[i+2][j]+w[i+1]$。
• …
• 根節點在$k$位置，得到的分數為$f[i][k?1]\times f[k+1][j]+w[k]$。
• …
• 根節點在$j$位置，此時右子樹為空，加分為$1\times$，得到的分數為$f[i][j?1]\times 1+w[j]$。

這里$w[i]$表示第$i$個節點的分數。$f[i][j]$要取以上情況的最大值。

初始狀態

• 空樹其加分為$1$，也就是說$f[i][i?1]=1$（或者$f[i+1][i]=1$）
• 如果區間只有一個節點，那么分值就是當前節點的分數，即$f[i][i]=w[i]$

時間復雜度

狀態數為$n\times n$，狀態計算需要枚舉根節點的位置$1$ ~ $n$，時間復雜度為$O(n^3)$。

前序遍歷

為了找到最大加分的前序遍歷，就要在區間$[i,j]$中找到一個根節點$k$使得$f[i][k?1]\times f[k+1][j]+w[k]$等于$f[i][j]$。

對于前序遍歷要先輸出根節點$k$，然后在遞歸遍歷左子樹（$[i,k?1]$）和右子樹（$[k+1,j]$）即可。

注意，如果$i$和$j$相等，說明是葉子節點，其子樹的根節點就是自己。

代碼實現

#include <iostream>
using namespace std;
const int N = 50;
int w[N], f[N][N];
int n;
//求區間[i,j]的前序遍歷
void dfs(int i, int j)
{if(i > j) return; //空二叉樹if(i == j) cout << i << " "; //葉子節點else{//枚舉根節點for(int k = i; k <= j; k ++){//如果以k為根節點取得加分最大值if(f[i][j] == f[i][k - 1] * f[k + 1][j] + w[k]) {cout << k << " "; //輸出根節點dfs(i, k - 1); //遞歸遍歷左子樹dfs(k + 1, j); //遞歸遍歷右子樹break;}}}
}int main()
{cin >> n;for(int i = 1; i <= n; i ++) cin >> w[i];//空樹的加分為1for(int i = 1; i <= n + 1; i ++) f[i][i - 1] = 1;//枚舉合并長度for(int len = 1; len <= n; len ++){//枚舉開始位置for(int i = 1; i + len - 1 <= n; i ++){int j = i + len - 1; //結束位置if(len == 1) f[i][i] = w[i]; //初始狀態else{//枚舉其它根節點的位置for(int k = i; k <= j; k ++)f[i][j] = max(f[i][j], f[i][k - 1] * f[k + 1][j] + w[k]);}            }}cout << f[1][n] << '\n';dfs(1, n);return 0;
}