試題鏈接：

文章目錄

• • 題目描述
  • 題解：
  • 代碼：

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 131072K，其他語言262144K 64bit IO Format: %lld

題目描述

設一個n個節點的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數字1,2,3,…,n為節點編號。每個節點都有一個分數（均為正整數），記第j個節點的分數為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數若某個子樹為主，規定其加分為1，葉子的加分就是葉節點本身的分數。不考慮它的空子樹。 試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。 要求輸出： （1）tree的最高加分 （2）tree的前序遍歷

輸入描述:

第1行：一個整數n（n＜30），為節點個數。 第2行：n個用空格隔開的整數，為每個節點的分數（分數＜100）。

輸出描述:

第1行：一個整數，為最高加分（結果不會超過4,000,000,000）。 第2行：n個用空格隔開的整數，為該樹的前序遍歷。

示例1
輸入

5 5 7 1 2 10

輸出

145 3 1 2 4 5

題解：

這個題沒大看明白。。。
樣例分析一陣子也沒算出145（我太菜了 ）

---

更新：
看了其他題解后，逐漸明白一點
記憶化搜索

f [ l ] [ r ] 表示這顆樹中序遍歷中第l個節點到第r個節點為一顆子樹的得分最大值
中序遍歷中根的左邊就是左子樹，右邊就是右子樹，對每一顆子樹枚舉根節點k為位置，左子樹的編號都小于根節點，右子樹都大于根節點，
枚舉根k，左子樹l…k-1
右子樹 k+1…r
區間為連續的，直接使用f [ i ] [ k-1 ] 與 f [ k+1 ] [ j ]，兩者相乘就行

f [ i ] [ j ] = max ( f [ i ] [ k-1 ] * f [ k+1 ] [ j ] + tree [ k ])
f [ i ] [ k-1 ] 表示左節點
f [ k+1 ] [ j ]表示右節點

我們再用一個根節點數組root [ i ][ j ] 表示區間i到j選擇的根節點是什么

邊界為k = = i或者k = = j的時候的情況。

代碼：

#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=31; int tree[maxn],f[maxn][maxn],n; inline void dfs(int l,int r){if(l>r)return;if(l==r){printf("%d ",l);return;}for(int i=l;i<=r;++i){if(f[l][r]==f[l][i-1]*f[i+1][r]+tree[i]){cout<<i<<" "; dfs(l,i-1);dfs(i+1,r);return;}} } inline void dfs1(){f[n+1][n]=1;for(int i=n;i;--i){for(int j=i+1;j<=n;++j){for(int k=i;k<=j;++k){f[i][j]=max(f[i][j],f[i][k-1]*f[k+1][j]+tree[k]);}}}cout<<f[1][n]<<endl; } int main(){cin>>n;for(int i=1;i<=n;++i){cin>>tree[i];f[i][i]=tree[i];f[i][i-1]=1;}dfs1();dfs(1,n);return 0; }

總結

以上是生活随笔為你收集整理的牛客网 【每日一题】5月13日 加分二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。