題目描述

設一個n個節點的二叉樹tree的中序遍歷為（1,2,3,…,n），其中數字1,2,3,…,n為節點編號。每個節點都有一個分數（均為正整數），記第i個節點的分數為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

輸出樣例#1：

145 3 1 2 4 5

源代碼

#include<iostream> using namespace std;int dp[35][35],pre[35][35]; void print(int l,int r);int main() {int n;int score[31];int len,i,j,k;int x;cin>>n;//輸入節點數for(i=1;i<=n;i++)//輸入節點分數cin>>score[i];for(i=1;i<=n;i++){dp[i][i]=score[i];//存儲子樹的最大加分pre[i][i]=i;//存儲根節點}for(len=1;len<=n;len++)//len:子樹結點數{for(i=1;i+len<=n;i++)//子樹最左端的結點 {j=len+i;//子樹最右端的結點 x=score[j]+dp[i][j-1];//j加僅一棵子樹的情況 dp[i][j]=score[i]+dp[i+1][j];//i加僅一棵子樹的情況 pre[i][j]=i;if(dp[i][j]<x){dp[i][j]=x;pre[i][j]=j;}for(k=i+1;k<j;k++)//兩棵子樹的情況,k:根節點 {x=score[k]+dp[i][k-1]*dp[k+1][j];if(dp[i][j]<x){dp[i][j]=x;pre[i][j]=k;}} }}cout<<dp[1][n]<<endl;//輸出最高加分print(1,n);//輸出前序return 0; }void print(int l,int r) {if(l>r)return;cout<<pre[l][r]<<" ";//根結點輸出if(l==r) return;print(l,pre[l][r]-1);print(pre[l][r]+1,r); }

?

總結

以上是生活随笔為你收集整理的加分二叉树（洛谷-P1040）的全部內容，希望文章能夠幫你解決所遇到的問題。

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