💐The Begin💐點點關(guān)注，收藏不迷路💐

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

輸入

第1行：一個整數(shù)n（n＜30），為節(jié)點個數(shù)。
第2行：n個用空格隔開的整數(shù)，為每個節(jié)點的分?jǐn)?shù)（分?jǐn)?shù)＜100）。

輸出

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

樣例輸入

5
5 7 1 2 10

樣例輸出

145
3 1 2 4 5  

以下是用 C 語言實現(xiàn)的代碼：

#include <stdio.h>#define MAX_NODE 60// 定義最大節(jié)點數(shù)
int score[MAX_NODE][MAX_NODE]; // score 存儲子樹的最大加分
int midNode[MAX_NODE][MAX_NODE]; // midNode 存儲子樹最大加分時的根節(jié)點位置
int nodeVal[MAX_NODE]; // nodeVal 存儲節(jié)點的分?jǐn)?shù)
int numNodes; // numNodes 代表節(jié)點總數(shù)// 遞歸計算最大加分函數(shù)
int findMaxScore(int start, int end) {// 如果區(qū)間無效，返回 1if (start > end)return 1;// 如果已經(jīng)計算過該區(qū)間的最大加分，直接返回結(jié)果if (score[start][end])return score[start][end];// 如果區(qū)間只有一個節(jié)點，最大加分就是該節(jié)點的分?jǐn)?shù)if (start == end) {score[start][end] = nodeVal[start];} else {int tempScore;for (int i = start; i <= end; ++i) {// 遞歸計算左右子樹的最大加分并加上當(dāng)前節(jié)點的分?jǐn)?shù)tempScore = findMaxScore(start, i - 1) * findMaxScore(i + 1, end) + nodeVal[i];// 更新最大加分和對應(yīng)的中間節(jié)點if (tempScore > score[start][end]) {score[start][end] = tempScore;midNode[start][end] = i;}}}return score[start][end];
}// 輸出前序遍歷函數(shù)
void printPreorder(int start, int end) {// 如果區(qū)間無效，直接返回if (start > end)return;// 如果區(qū)間只有一個節(jié)點，直接輸出該節(jié)點if (start == end) {printf("%d ", start);} else {// 輸出中間節(jié)點printf("%d ", midNode[start][end]);// 遞歸輸出左子樹和右子樹printPreorder(start, midNode[start][end] - 1);printPreorder(midNode[start][end] + 1, end);}
}int main() {scanf("%d", &numNodes);for (int i = 1; i <= numNodes; ++i) {scanf("%d", &nodeVal[i]);}printf("%d\n", findMaxScore(1, numNodes));printPreorder(1, numNodes);return 0;
}

以下是用 C++實現(xiàn)的代碼：

#include <iostream>const int MAX_N = 60;// 定義最大節(jié)點數(shù)
int score[MAX_N][MAX_N]; // score 存儲子樹的最大加分
int midNode[MAX_N][MAX_N]; // midNode 存儲子樹最大加分時的根節(jié)點位置
int nodeVal[MAX_N]; // nodeVal 存儲節(jié)點的分?jǐn)?shù)
int numNodes; // numNodes 代表節(jié)點總數(shù)// 遞歸計算最大加分函數(shù)
int findMaxScore(int start, int end) {// 如果區(qū)間無效，返回 1if (start > end)return 1;// 如果已經(jīng)計算過該區(qū)間的最大加分，直接返回結(jié)果if (score[start][end])return score[start][end];// 如果區(qū)間只有一個節(jié)點，最大加分就是該節(jié)點的分?jǐn)?shù)if (start == end) {score[start][end] = nodeVal[start];} else {int tempScore;for (int i = start; i <= end; ++i) {// 遞歸計算左右子樹的最大加分并加上當(dāng)前節(jié)點的分?jǐn)?shù)tempScore = findMaxScore(start, i - 1) * findMaxScore(i + 1, end) + nodeVal[i];// 更新最大加分和對應(yīng)的中間節(jié)點if (tempScore > score[start][end]) {score[start][end] = tempScore;midNode[start][end] = i;}}}return score[start][end];
}// 輸出前序遍歷函數(shù)
void printPreorder(int start, int end) {// 如果區(qū)間無效，直接返回if (start > end)return;// 如果區(qū)間只有一個節(jié)點，直接輸出該節(jié)點if (start == end) {std::cout << start << " ";} else {// 輸出中間節(jié)點std::cout << midNode[start][end] << " ";// 遞歸輸出左子樹和右子樹printPreorder(start, midNode[start][end] - 1);printPreorder(midNode[start][end] + 1, end);}
}int main() {std::cin >> numNodes;for (int i = 1; i <= numNodes; ++i) {std::cin >> nodeVal[i];}std::cout << findMaxScore(1, numNodes) << std::endl;printPreorder(1, numNodes);return 0;
}

以下是用 Java 實現(xiàn)的代碼：

import java.util.Scanner;class BinaryTreeScoreCalculator {// 定義最大節(jié)點數(shù)private static final int MAX_N = 60;// 存儲子樹的最大加分static int[][] score = new int[MAX_N][MAX_N];// 存儲子樹最大加分時的根節(jié)點位置static int[][] midNode = new int[MAX_N][MAX_N];// 存儲節(jié)點的分?jǐn)?shù)static int[] nodeVal = new int[MAX_N];// 代表節(jié)點總數(shù)static int numNodes;// 遞歸計算最大加分函數(shù)static int findMaxScore(int start, int end) {// 如果區(qū)間無效，返回 1if (start > end)return 1;// 如果已經(jīng)計算過該區(qū)間的最大加分，直接返回結(jié)果if (score[start][end]!= 0)return score[start][end];// 如果區(qū)間只有一個節(jié)點，最大加分就是該節(jié)點的分?jǐn)?shù)if (start == end) {score[start][end] = nodeVal[start];} else {int tempScore;for (int i = start; i <= end; ++i) {// 遞歸計算左右子樹的最大加分并加上當(dāng)前節(jié)點的分?jǐn)?shù)tempScore = findMaxScore(start, i - 1) * findMaxScore(i + 1, end) + nodeVal[i];// 更新最大加分和對應(yīng)的中間節(jié)點if (tempScore > score[start][end]) {score[start][end] = tempScore;midNode[start][end] = i;}}}return score[start][end];}// 輸出前序遍歷函數(shù)static void printPreorder(int start, int end) {// 如果區(qū)間無效，直接返回if (start > end)return;// 如果區(qū)間只有一個節(jié)點，直接輸出該節(jié)點if (start == end) {System.out.print(start + " ");} else {// 輸出中間節(jié)點System.out.print(midNode[start][end] + " ");// 遞歸輸出左子樹和右子樹printPreorder(start, midNode[start][end] - 1);printPreorder(midNode[start][end] + 1, end);}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);numNodes = scanner.nextInt();for (int i = 1; i <= numNodes; ++i) {nodeVal[i] = scanner.nextInt();}System.out.println(findMaxScore(1, numNodes));printPreorder(1, numNodes);}
}

💐The End💐點點關(guān)注，收藏不迷路💐