CODEVS1090 加分二叉树
2024-08-26 20:58:19
codevs1090 加分二叉树
2003年NOIP全国联赛提高组
题目描述 Description
设一个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的最高加分
现在,请你帮助你的好朋友XZ设计一个程序,求得正确的答案。
输入描述 Input Description
第1行:一个整数n(n<=30),为节点个数。
第2行:n个用空格隔开的整数,为每个节点的分数(分数<=100)
输出描述 Output Description
第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。
样例输入 Sample Input
5
5 7 1 2 10
样例输出 Sample Output
145
数据范围及提示 Data Size & Hint
n(n<=30)
分数<=100
【题解】
首先大多数关于中序遍历的题都有一个特点就是要枚举根节点,中序遍历中在根节点前的在左子树,后面的在右子树
树形dp,dp[i]=以这个为根节点的二叉树的最大分值
dp[i]=max(dp[左子树],dp[右子树])
先枚举根节点再递归做左右子树
最后max(dp[i])就是正解
最新文章
- 获取CPU信息
- oracle存储过程实现根据已有数据批量更新另一批数据
- 用Sqlplus手动创建Oracle11g数据库
- 精品手游《里奥的财富》高清版逆向移植家用机与PC平台(转)
- 【转】ConcurrentHashMap完全解析(JDK6/7、JDK8)
- uml与数据库设计
- SQL2008数据库连接服务器为主机名时连接成功,服务器为Ip地址时链接失败
- Spring jdbctemplate学习笔记
- Android设计中的.9.png与Android Studio中的设置
- [SVN]常见问题的解决方案
- <;EditText />; This text field does not specify an inputType or a hint
- 最小生成树之Prim算法
- JS的深度克隆,利用构造函数原型深度克隆
- LZO
- 【MAC】Mac下部分常用的小工具
- windows程序设计 创建一个新的窗口
- Delphi 的 Bit
- Docker Compose 版本过高(Docker版本不匹配),降低docker-compose版本
- AJAX其实就是一个异步网络请求
- spring+springMVC+Mybatis 中使用@Transcational方式管理事务的配置方法