wordpress大學(xué)主題下載地址恩施seo整站優(yōu)化哪家好
【NOIP提高組】加分二叉樹
💐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)注,收藏不迷路💐 |