网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
加分二叉树
成绩 | 100 | 开启时间 | 2016年05月31日 星期二 10:40 |
折扣 | 0.8 | 折扣时间 | 2016年05月31日 星期二 10:40 |
允许迟交 | 是 | 关闭时间 | 2016年05月31日 星期二 10:40 |
输入文件 | tree.in | 输出文件 | tree.out |
【题目描述】加分二叉树(tree.cpp/c/pas)NOIP 2003
科技忽略了过程就是魔法,魔法展示了过程就是科技。例如,在魔法世界彪炳史册的艾萨克·牛顿爵士,就被称为“最初的科学家,最后的炼金术士”。魔法世界的所谓魔法,其本质就是科技,只不过因为在远古时代发生的几次战乱,导致相当数量尖端科技理论的遗失和残缺,使得人们只知道如何使用科技却无法解释其原理,只好统称为魔法而已。所以魔法世界的科技树在宇宙各种文明的发展中,可以抽象的看成一颗奇怪的具有n个节点的二叉树tree,树的中序遍历为(l,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行:一个整数,为最高加分(结果不会超过4000 000 000)。 第2行:n个用空格隔开的整数,为该树的前序遍历。
【输入样例】
5
5 7 1 2 10
【输出样例】
145
3 1 2 4 5