P1040 加分二叉樹

題目描述

設一個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

分析：

二叉樹的中序遍歷是把根節點放在中間

換而言之就是把根節點左右兩邊的樹形序列(子樹)合并起來

那決策點就是根節點

那么很明顯這道題就是一個合并類的區間DP了

和石子合并思路相同，需要注意的是初始狀態必須為1(因為是相乘)，不然結果會出錯

dp[i][j]表示中序遍歷i到j最大值

方程：dp[i,j]:=max(dp[i][k-1]*dp[k+1][j]+dp[k][k]

1 #include

2 #include

3 #include

4

5 #define N 101

6

7 using namespacestd;8 intn,num[N][N];9 long longf[N][N];10

11 void find(int x,inty)12 {13 if(x<=y)14 {15 printf("%d",num[x][y]);16 find(x,num[x][y]-1);17 find(num[x][y]+1,y);18 }19 }20

21 intmain()22 {23 scanf("%d",&n);24 //f用來dp，num用來記錄路徑

25 for(int i=0;i<=n;i++) for(int j=0;j<=n;j++)26 {27 //初始時把每個節點都看做是葉子節點28 //初始時把每個節點的根都看出是自己

29 f[i][j]=1;num[i][i]=i;30 }31 //輸入節點 歷i到i的值就是葉子節點的值

32 for(int i=1;i<=n;i++) scanf("%d",&f[i][i]);33 //區間DP合并石子的一種寫法里面的

34 for(int i=n;i>=1;i--)35 for(int j=i+1;j<=n;j++)36 for(int k=i;k<=j;k++)37 {38 if(f[i][j]

41 num[i][j]=k;42

43 }44 printf("%lld\n",f[1][n]);find(1,n);45 return 0;46 }

總結

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

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