我要招人

去企业版

首页 > 试题广场 >

打家劫舍(三)

[编程题]打家劫舍(三)

热度指数：1047 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

你是一个经验丰富的小偷，经过上次在街边和湖边得手后你准备挑战一次自己，你发现了一个结构如二叉树的小区，小区内每个房间都存有一定现金，你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。

问，给定一个二叉树结构的小区，如之前两次行动一样，你无法在不触动警报的情况下同时偷窃两个相邻的房间，在不触动警报的情况下最多的偷窃金额。

1.如果输入的二叉树是

2 1 2 2 1

0 1 1 2 3

那么形状结构如下:

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

2.如果输入的二叉树是

3 2 10

0 1 1

那么形状结构如下:

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

数据范围：二叉树节点数量满足 $1 \le n \le 10^5 \$ ，树上的值满足 $1 \le nums[i] \le 5000 \$

输入描述:

第一行输入一个正整数 n 表示节点的数量。
第二行输入 n 个正整数，其中第 i 个节点表示序号是 i 的节点的值。
第三行输入 n 个整数，其中第 i 个数表示序号是 i 的节点的父节点的序号。（0表示是根节点）

输出描述:

输出最优方案的的偷窃金额。

示例1

输入

5
2 1 2 2 1
0 1 1 2 3

输出

示例2

输入

3
3 2 10
0 1 1

输出

算法知识视频讲解

静寂旮旯

发表于 2022-06-04 20:36:17

解题思路：题目规定不能连续相邻两个房间偷，令dpi,0/1dp_{i,0/1}dpi,0/1来表示节点iii为根可以偷到的最大价值，最终结果即max⁡(dp1,0,dp1,1)\max(dp_{1,0},dp_{1,1})max(dp1,0,dp1,1)。假设iii被偷，则有：dpi,1 展开全文

朱越峰

发表于 2022-04-21 17:21:10

本题会有大规模测试用例，用深度优先搜索可能会超出迭代次数上限。也许可以通过手动指定迭代次数上限来解决这个问题，但我选择维护动态规划列表。本质上和前两道打家劫舍没有什么区别，难度虚高了。 n = int(input()) pts = list(map(int, input().split())) 展开全文

理塘_丁真

发表于 2022-07-01 23:36:52

扎西德勒 #include<iostream> #include<vector> #include<unordered_map> using namespace std; int n; vector<vector<in 展开全文

牛客494732号

发表于 2023-05-24 11:25:48

package main import ( "bufio" "fmt" "os" ) var in = bufio.NewReader(os.Stdin) var out = bufio.NewWriter(os.Stdout) func ReadInt(a *int) error{ 展开全文

枩

发表于 2023-02-24 13:38:39

const rl = require("readline").createInterface({ input: process.stdin }); const inputs = []; rl.on('line', (line) => { inputs.push(line); }). 展开全文

赫he

发表于 2023-09-18 20:47:53

树状dp，一般需要遍历树。方式是深度遍历。这个题，节点用输入数值的下标来表示，如图所示： f[i][0]表示以i为根的子树，并且不包括节点i（最大值不包括节点的值）的最大值，该状态可以来自于左右子树（如果存在）的max(f[左子树][0], f[左子树][1])+max(f[右子树][0], 展开全文