在线评测链接:P1190 (opens new window)
# 题目内容
塔子哥设计的这个游戏是一个冒险类游戏,参与者需要在地图上寻找食物并获得尽可能多的食物,同时需要注意在游戏过程中所处的位置,因为不同的位置可以通过传送门到达其他位置,可能会影响食物获取的数量。
在游戏开始时,参与者会出发点选择一个方格作为起点,每个方格上至多 个传送门,通过传送门可将参与者传送至指定的其它方格。每个方格上都标注了三个数字:id
、 parent-id
和 value
。其中, id
代表方格的编号, parent-id
代表可以通过传送门到达该方格的方格编号, value
代表在该方格获取或失去的食物单位数。
参与者需要在地图上行进,到达每个方格并获取或失去对应的食物单位数,直到满足退出游戏的条件之一。参与者的最终得分是所获取食物单位数的总和,需要尽可能地高。
需要注意的是地图设计时保证了参与者不可能到达相同的方格两次。因此,参与者当前所处的方格无传送门,游戏将立即结束。另外,参与者在任意方格上都可以宣布退出游戏,同样会结束游戏。
请计算参与者退出游戏后,最多可以获得多少单位的食物。
# 输入描述
第一行:方块个数 ( )
接下来 行,每行三个整数 id
, parent-id
, value
,具体含义见题面。
,
特殊的 parent-id
可以取 则表示没有任何方格可以通过传送门传送到此方格,这样的方格在地图中有且仅有一个。
# 输出描述
输出为一个整数,表示参与者退出游戏后最多可以获得多少单位的食物。
# 样例
输入
7
0 1 8
1 -1 -2
2 1 9
4 0 -2
5 4 3
3 0 -3
6 2 -3
输出
9
样例解释
参与者从方格 出发,通过传送门到达方格 ,再通过传送门到达方格 。一共获得 个单位食物,得到食物最多或者参与者在游戏开始时处于方格 ,直接主动宣布退出游戏,也可以获得 个单位食物。
# 样例2
输入
3
0 -1 3
1 0 1
2 0 2
输出
5
样例解释
参与者从方格 出发,通过传送门到达方格 ,一共可以获得 个单位食物,此时得到食物最多。
# 思路
# 简单树上dp
解题方法为dfs递归求解,定义 表示从 点出发能获得的最多的食物,在该定义下, 的初始值为 , 为在该点能够获得的食物(从 出发,意味着已经在该点上,因此该点获得食物为初始值)。
由于参与者能够在任意方格上宣布结束,这就意味着子树可走可不走。
那么对于任意一个节点 ,,其中 为 的子节点。
时间复杂度:
# 类似题目推荐
# LeetCode
# CodeFun2000
难度依次递增
P1141 2023.04.01 美团春招-第五题-染色の树 (opens new window)
P1150 2023.03.30-拼多多-第二题-修复道路 (opens new window)
P1193 2023.04.13-腾讯音乐-暑期实习-第二题-价值二叉树 (opens new window)
P1081 2023.3.13-百度-第三题-树上同色连通块 (opens new window)
# 代码
# CPP
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e4+10;
int n;
int a[maxn],dp[maxn];
int head[maxn],ver[maxn<<1],Next[maxn<<1],tot=1;
int ans=-1e9;
void add(int x,int y){//链式前向星存储图
ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
}
void dfs(int x){
dp[x]=a[x];
for(int i=head[x],y;i;i=Next[i]){
y=ver[i];
dfs(y);
dp[x]=max(dp[y]+a[x],dp[x]);
ans=max(ans,dp[x]);//更新答案
}
}
int main(){
scanf("%d",&n);
int root;
for(int i=0,x,y;i<n;++i){
scanf("%d %d",&x,&y);
scanf("%d",a+x);
if(y!=-1) add(y,x);
else root=x;
}
dfs(root);
printf("%d",ans);
return 0;
}
# python
# 使用链式前向星存储图
def add(x, y):
global tot
ver.append(y)
Next.append(head[x])
head[x] = tot
tot += 1
# 深度优先搜索
def dfs(x):
global ans
dp[x] = a[x]
i = head[x]
while i:
y = ver[i]
dfs(y)
dp[x] = max(dp[y] + a[x], dp[x])
ans = max(ans, dp[x]) # 更新答案
i = Next[i]
n = int(input())
maxn = 10010
a = [0] * maxn
dp = [0] * maxn
head = [0] * maxn
ver = []
Next = []
tot = 1
ans = -1e9
root = 0
for _ in range(n):
x, y = map(int, input().split())
a[x] = int(input())
if y != -1:
add(y, x)
else:
root = x
dfs(root)
print(ans)
# Java
import java.util.Scanner;
public class Main {
static final int maxn = 10010;
static int n;
static int[] a = new int[maxn];
static int[] dp = new int[maxn];
static int[] head = new int[maxn];
static int[] ver = new int[maxn << 1];
static int[] Next = new int[maxn << 1];
static int tot = 1;
static int ans = -1000000000;
// 使用链式前向星存储图
static void add(int x, int y) {
ver[++tot] = y;
Next[tot] = head[x];
head[x] = tot;
}
static void dfs(int x) {
dp[x] = a[x];
for (int i = head[x]; i != 0; i = Next[i]) {
int y = ver[i];
dfs(y);
dp[x] = Math.max(dp[y] + a[x], dp[x]);
ans = Math.max(ans, dp[x]); // 更新答案
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
int root = 0;
for (int i = 0; i < n; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
a[x] = scanner.nextInt();
if (y != -1) {
add(y, x);
} else {
root = x;
}
}
dfs(root);
System.out.println(ans);
}
}
# Go
package main
import "fmt"
const maxn = 10010
var (
n int
a [maxn]int
dp [maxn]int
head [maxn]int
ver [maxn << 1]int
Next [maxn << 1]int
tot = 1
ans = -1000000000
)
// 使用链式前向星存储图
func add(x, y int) {
ver[tot] = y
Next[tot] = head[x]
head[x] = tot
tot++
}
func dfs(x int) {
dp[x] = a[x]
for i := head[x]; i != 0; i = Next[i] {
y := ver[i]
dfs(y)
dp[x] = max(dp[y]+a[x], dp[x])
ans = max(ans, dp[x]) // 更新答案
}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
fmt.Scan(&n)
root := 0
for i := 0; i < n; i++ {
var x, y int
fmt.Scan(&x, &y)
fmt.Scan(&a[x])
if y != -1 {
add(y, x)
} else {
root = x
}
}
dfs(root)
fmt.Println(ans)
}
# Js
const maxn = 10010;
let n;
const a = new Array(maxn).fill(0);
const dp = new Array(maxn).fill(0);
const head = new Array(maxn).fill(0);
const ver = new Array(maxn << 1).fill(0);
const Next = new Array(maxn << 1).fill(0);
let tot = 1;
let ans = -1000000000;
function add(x, y) {
ver[tot] = y;
Next[tot] = head[x];
head[x] = tot;
tot++;
}
function dfs(x) {
dp[x] = a[x];
let i = head[x];
while (i !== 0) {
const y = ver[i];
dfs(y);
dp[x] = Math.max(dp[y] + a[x], dp[x]);
ans = Math.max(ans, dp[x]); // 更新答案
i = Next[i];
}
}
function main() {
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('Enter the value of n: ', (value) => {
n = parseInt(value);
let root = 0;
const inputArr = [];
rl.prompt();
rl.on('line', (line) => {
inputArr.push(line.trim());
if (inputArr.length === n) {
rl.close();
}
}).on('close', () => {
for (let i = 0; i < n; i++) {
const inputLine = inputArr[i].split(' ');
const x = parseInt(inputLine[0]);
const y = parseInt(inputLine[1]);
a[x] = parseInt(inputLine[2]);
if (y !== -1) {
add(y, x);
} else {
root = x;
}
}
dfs(root);
console.log(ans);
process.exit(0);
});
});
}
main();