《题目版_深入分析区间型动态规划》由会员分享，可在线阅读，更多相关《题目版_深入分析区间型动态规划（2页珍藏版）》请在金锄头文库上搜索。
2、加分二叉树【问题描述】设一个 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（n30），为节点个数。第 2 行：n 个用空格隔开的整数，为每个节点的分数（分数100）。【输出格式】第 1 行：一个整数，为最高加分（结果不会超过4,000,000,000）。第 2 行：n 个用空格隔开的整数，为该树的前序遍历。【输入样例】55 7 1 2 10【输出样例】1453 1 2 4 5
