首页 > 试题广场 >

打家劫舍(三)

[编程题]打家劫舍(三)
  • 热度指数:1047 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。
问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。

1.如果输入的二叉树是
5
2 1 2 2 1
0 1 1 2 3
那么形状结构如下:


小区入口的房间的值是2 ,偷窃第一层2和第三层 2,1 是最优方案。


2.如果输入的二叉树是
3
3 2 10
0 1 1
那么形状结构如下:

样例2:小区入口的房间的值是3 ,偷窃第二层 2,10 是最优方案。

数据范围:二叉树节点数量满足 ,树上的值满足

输入描述:
第一行输入一个正整数 n 表示节点的数量。
第二行输入 n 个正整数,其中第 i 个节点表示序号是 i 的节点的值。
第三行输入 n 个整数,其中第 i 个数表示序号是 i 的节点的父节点的序号。(0表示是根节点)



输出描述:
输出最优方案的的偷窃金额。
示例1

输入

5
2 1 2 2 1
0 1 1 2 3

输出

5
示例2

输入

3
3 2 10
0 1 1

输出

12

这道题你会答吗?花几分钟告诉大家答案吧!

问题信息

难度:
0条回答 1471浏览

热门推荐

通过挑战的用户

查看代码