題目描述
原題鏈接
分析
題目所求是一棵符合中序遍歷且加分最高的二叉樹, 而二叉樹的加分 \(=\) 左子樹的加分 \(×\) 右子樹的加分 \(+\) 根的分數?
假設求一棵根節點是\(k\)的加分最高的二叉樹,由于根的分數已經確定,則要使其左子樹加分最高且右子樹加分最高
如何使其左子樹加分最高呢?(右子樹同理)
首先要在\([1,k-1]\)(為什么是\([1,k-1]?\) 因為在中序序列中, 根節點左邊是其左子樹, 右邊是其右子樹)列舉左子樹的根\(j\), 且使以\(j\)為根節點的二叉樹的左子樹加分最高且右子樹加分最高.
所以求二叉樹的最高加分其實是一個不斷進行遞回的程序, 可以用區間DP來解決
區間DP思路如下:
題目還讓求一個加分最高的二叉樹的前序遍歷, 且字典序最小
如何求前序遍歷? 在區間DP的程序中,每一次從\([i,j]\)劃分出的若干類中選出的最優的第\(k\)類, 其實就可以確定\([i,j]\)的根節點是\(k\), 再確定其左右子樹的根節點, 從而遞回求出前序遍歷
如何保證字典序最小? 注意到求前序遍歷的程序實際上是選擇根節點的程序, 則保證每次選出的根節點最小即可
看不懂就參考Y總視頻講解
實作
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 35;
int n;
int a[N];
int f[N][N]; // f[i][j] 表示 中序遍歷是[i,j]所有二叉樹的集合 的最大加分
int root[N][N]; // 記錄[i,j]的根節點
void dfs(int l, int r)
{
if(l > r) return;
int k = root[l][r];
cout << k << " ";
dfs(l,k-1);
dfs(k+1,r);
return;
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
for(int len = 1; len <= n; len++) // 列舉區間長度
{
for(int i=1; i + len - 1 <= n; i++) // 列舉區間左端點
{
int j = i + len - 1; // 確定區間右端點
for(int k=i; k<=j; k++ ) // 列舉根節點
{
int left_score = k==i ? 1 : f[i][k-1]; // 確定左子樹的加分(當左子樹為空(k == i), 規定加分為1)
int right_score = k==j ? 1 : f[k+1][j]; // 確定右子樹的加分
// 確定以K為根節點的二叉樹的加分,葉子(i==j)的加分就是葉節點本身的分數,不考慮它的空子樹，
int k_score = i == j ? a[k] : left_score * right_score + a[k];
if(f[i][j] < k_score)
{
f[i][j] = k_score;
root[i][j] = k;
}
}
}
}
cout << f[1][n] << endl;
dfs(1,n); // 輸出前序序列
system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259929.html
標籤：其他
上一篇：性能測驗整體認知