【NOIP提高组】加分二叉树

💐The Begin💐点点关注，收藏不迷路💐

在这里插入图片描述

设一个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个用空格隔开的整数，为该树的前序遍历。

样例输入

5
5 7 1 2 10

样例输出

145
3 1 2 4 5

以下是用 C 语言实现的代码：

#include <stdio.h>#define MAX_NODE 60// 定义最大节点数
int score[MAX_NODE][MAX_NODE]; // score 存储子树的最大加分
int midNode[MAX_NODE][MAX_NODE]; // midNode 存储子树最大加分时的根节点位置
int nodeVal[MAX_NODE]; // nodeVal 存储节点的分数
int numNodes; // numNodes 代表节点总数// 递归计算最大加分函数
int findMaxScore(int start, int end) {// 如果区间无效，返回 1if (start > end)return 1;// 如果已经计算过该区间的最大加分，直接返回结果if (score[start][end])return score[start][end];// 如果区间只有一个节点，最大加分就是该节点的分数if (start == end) {score[start][end] = nodeVal[start];} else {int tempScore;for (int i = start; i <= end; ++i) {// 递归计算左右子树的最大加分并加上当前节点的分数tempScore = findMaxScore(start, i - 1) * findMaxScore(i + 1, end) + nodeVal[i];// 更新最大加分和对应的中间节点if (tempScore > score[start][end]) {score[start][end] = tempScore;midNode[start][end] = i;}}}return score[start][end];
}// 输出前序遍历函数
void printPreorder(int start, int end) {// 如果区间无效，直接返回if (start > end)return;// 如果区间只有一个节点，直接输出该节点if (start == end) {printf("%d ", start);} else {// 输出中间节点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++实现的代码：

#include <iostream>const int MAX_N = 60;// 定义最大节点数
int score[MAX_N][MAX_N]; // score 存储子树的最大加分
int midNode[MAX_N][MAX_N]; // midNode 存储子树最大加分时的根节点位置
int nodeVal[MAX_N]; // nodeVal 存储节点的分数
int numNodes; // numNodes 代表节点总数// 递归计算最大加分函数
int findMaxScore(int start, int end) {// 如果区间无效，返回 1if (start > end)return 1;// 如果已经计算过该区间的最大加分，直接返回结果if (score[start][end])return score[start][end];// 如果区间只有一个节点，最大加分就是该节点的分数if (start == end) {score[start][end] = nodeVal[start];} else {int tempScore;for (int i = start; i <= end; ++i) {// 递归计算左右子树的最大加分并加上当前节点的分数tempScore = findMaxScore(start, i - 1) * findMaxScore(i + 1, end) + nodeVal[i];// 更新最大加分和对应的中间节点if (tempScore > score[start][end]) {score[start][end] = tempScore;midNode[start][end] = i;}}}return score[start][end];
}// 输出前序遍历函数
void printPreorder(int start, int end) {// 如果区间无效，直接返回if (start > end)return;// 如果区间只有一个节点，直接输出该节点if (start == end) {std::cout << start << " ";} else {// 输出中间节点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 实现的代码：

import java.util.Scanner;class BinaryTreeScoreCalculator {// 定义最大节点数private static final int MAX_N = 60;// 存储子树的最大加分static int[][] score = new int[MAX_N][MAX_N];// 存储子树最大加分时的根节点位置static int[][] midNode = new int[MAX_N][MAX_N];// 存储节点的分数static int[] nodeVal = new int[MAX_N];// 代表节点总数static int numNodes;// 递归计算最大加分函数static int findMaxScore(int start, int end) {// 如果区间无效，返回 1if (start > end)return 1;// 如果已经计算过该区间的最大加分，直接返回结果if (score[start][end]!= 0)return score[start][end];// 如果区间只有一个节点，最大加分就是该节点的分数if (start == end) {score[start][end] = nodeVal[start];} else {int tempScore;for (int i = start; i <= end; ++i) {// 递归计算左右子树的最大加分并加上当前节点的分数tempScore = findMaxScore(start, i - 1) * findMaxScore(i + 1, end) + nodeVal[i];// 更新最大加分和对应的中间节点if (tempScore > score[start][end]) {score[start][end] = tempScore;midNode[start][end] = i;}}}return score[start][end];}// 输出前序遍历函数static void printPreorder(int start, int end) {// 如果区间无效，直接返回if (start > end)return;// 如果区间只有一个节点，直接输出该节点if (start == end) {System.out.print(start + " ");} else {// 输出中间节点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);}
}