2023.04.12-暑期实习-第二题-获取最多食物

wangxuehui LV 9 @ 7 months ago

!!!!我终于写对了一次dfs+动态规划

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 1e4 + 10;

int n;
vector<int> val; // 每个节点的食物单位数
vector<vector<int>> edg; // 邻接表，表示从一个节点可以到达的节点
int dp[maxn]; // dp数组存储从每个节点出发能获得的最大食物数
int ans = -1e4; // 用于存储最大答案

// 深度优先搜索
void dfs(int u) {
    dp[u] = val[u]; // 当前节点至少可以获得自己的食物值
    for (int v : edg[u]) {
        dfs(v); // 递归访问子节点
        dp[u] = max(dp[u], val[u] + dp[v]); // 更新当前节点的最大食物值
        
    }
    ans = max(ans, dp[u]); // 更新全局最大答案
}

int main() {
    cin >> n;
    val.resize(n+1);
    edg.resize(n+1);

    int start = -1; // 起点
    for (int i = 0; i < n; i++) {
        int id, pid, value;
        cin >> id >> pid >> value;
        val[id] = value; // 每个方格的食物数
        if (pid != -1) {
            edg[pid].push_back(id); // 建立从 pid 到 id 的边
        } else {
            start = id; // 找到起点
        }
    }

    // 从起点开始进行深度优先搜索
    dfs(start);

    cout << ans << endl; // 输出最大食物单位数

    return 0;
}

TaZi SU @ 8 months ago

题目大意

在一个冒险类游戏中，参与者可以在一个由多个方格构成的地图上寻找食物。每个方格有一个编号、一个父方格编号和对应的食物单位数。参与者可以通过传送门从一个方格移动到另一个方格。参与者可以选择任意方格作为起点，并可以在任何方格选择退出游戏。任务是计算参与者在退出时能够获得的最多食物单位数

思路

简单树上dp

1.数据结构设计：

使用邻接表来表示地图的结构，其中每个方格和其通过传送门可达的方格形成一个有向图。

2.输入处理：

读取方格的数量和每个方格的 id、parent-id、value，并构建邻接表。确定根节点（parent-id 为 -1 的方格）。

3.深度优先搜索（DFS）：

使用 DFS 遍历整个树，从根节点开始，计算从每个方格出发可以获取的最多食物单位数。对于每个方格，初始值为其自身的食物单位数。在访问子节点时，更新当前节点的食物总数为当前节点的食物数加上子节点的食物数。在更新食物总数时，考虑子树的选择，可能会选择不访问某个子节点以达到更高的总和。

4.结果输出：

记录在 DFS 遍历过程中能获得的最大食物单位数，并在最后输出结果。

时间复杂度： $O(N)$

代码说明

整体代码流程

1.输入读取：

读取方格数量 N 和每个方格的 id、parent-id、value，构建树的邻接表。

2.邻接表构建：

使用数组或链表来存储每个方格可以通过传送门到达的其他方格。

3.DFS 初始化：

定义一个数组来存储每个方格可以获得的食物总和。从根节点开始进行 DFS 遍历，计算每个节点的食物总和。

4.DFS 遍历：

递归访问每个方格，更新食物总数。处理子节点并更新当前节点的食物总数。

5.输出结果：

输出参与者能够获得的最多食物单位数。

代码

CPP

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 1e4 + 10; // 定义最大方格数量
int n; // 方格数量
int a[maxn], dp[maxn]; // a 用于存储每个方格的食物单位数，dp 用于存储从每个方格出发能获得的最多食物单位数
int head[maxn], ver[maxn << 1], Next[maxn << 1], tot = 1; // 图的邻接表
int ans = -1e9; // 初始化答案为负无穷大

// 添加边到邻接表
void add(int x, int y) {
    ver[++tot] = y; // 将 y 加入到 x 的邻接表
    Next[tot] = head[x]; // 记录原来的头节点
    head[x] = tot; // 更新头节点
}

// 深度优先搜索（DFS）
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); // 读取方格 id 和 parent-id
        scanf("%d", &a[x]); // 读取方格的食物单位数
        if (y != -1) add(y, x); // 如果 parent-id 不是 -1，添加边
        else root = x; // 否则记录根节点
    }
    dfs(root); // 从根节点开始 DFS
    printf("%d", ans); // 输出最大食物单位数
    
    return 0; // 程序结束
}

python

# 使用链式前向星存储图
def add(x, y):
    global tot
    ver.append(y)  # 将节点 y 添加到邻接表中
    Next.append(head[x])  # 将当前节点 x 的头指针保存到 Next 数组中
    head[x] = tot  # 更新节点 x 的头指针
    tot += 1  # 增加边的计数

# 深度优先搜索
def dfs(x):
    global ans
    dp[x] = a[x]  # 初始化当前节点的食物总数为其自身的食物单位数
    i = head[x]  # 从当前节点的头指针开始遍历
    while i:  # 只要 i 不为 0
        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())  # 读取方格 id 和 parent-id
    a[x] = int(input())  # 读取方格的食物单位数
    if y != -1:
        add(y, x)  # 如果 parent-id 不是 -1，添加边
    else:
        root = x  # 否则记录根节点

# 从根节点开始 DFS
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; // 将节点 y 添加到邻接表中
        Next[tot] = head[x]; // 将当前节点 x 的头指针保存到 Next 数组中
        head[x] = tot; // 更新节点 x 的头指针
    }

    // 深度优先搜索
    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(); // 读取方格 id
            int y = scanner.nextInt(); // 读取 parent-id
            a[x] = scanner.nextInt(); // 读取方格的食物单位数
            if (y != -1) { // 如果 parent-id 不是 -1，添加边
                add(y, x);
            } else { // 否则记录根节点
                root = x;
            }
        }
        dfs(root); // 从根节点开始 DFS
        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              // 将节点 y 添加到邻接表中
	Next[tot] = head[x]       // 将当前节点 x 的头指针保存到 Next 数组中
	head[x] = tot             // 更新节点 x 的头指针
	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) // 读取方格 id 和 parent-id
		fmt.Scan(&a[x])  // 读取方格的食物单位数
		if y != -1 { // 如果 parent-id 不是 -1，添加边
			add(y, x)
		} else { // 否则记录根节点
			root = x
		}
	}
	dfs(root) // 从根节点开始 DFS
	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; // 将节点 y 添加到邻接表中
    Next[tot] = head[x]; // 将当前节点 x 的头指针保存到 Next 数组中
    head[x] = tot; // 更新节点 x 的头指针
    tot++; // 增加边的计数
}

// 深度优先搜索
function dfs(x) {
    dp[x] = a[x]; // 初始化当前节点的食物总数为其自身的食物单位数
    let i = head[x]; // 从当前节点的头指针开始遍历
    while (i !== 0) { // 只要 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'); // 引入 readline 模块
    const rl = readline.createInterface({
        input: process.stdin, // 设置输入流
        output: process.stdout // 设置输出流
    });

    // 读取方格数量 n
    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) { // 如果输入行数达到 n
                rl.close(); // 关闭输入流
            }
        }).on('close', () => { // 输入流关闭后的处理
            // 处理输入的方格信息
            for (let i = 0; i < n; i++) {
                const inputLine = inputArr[i].split(' '); // 分割输入行
                const x = parseInt(inputLine[0]); // 读取方格 id
                const y = parseInt(inputLine[1]); // 读取 parent-id
                a[x] = parseInt(inputLine[2]); // 读取方格的食物单位数
                if (y !== -1) { // 如果 parent-id 不是 -1，添加边
                    add(y, x);
                } else { // 否则记录根节点
                    root = x;
                }
            }
            dfs(root); // 从根节点开始 DFS
            console.log(ans); // 输出最大食物单位数
            process.exit(0); // 退出进程
        });
    });
}

main(); // 调用主程序

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

动态规划

# Submissions

131

Accepted

Uploaded By

TaZi

2 solutions

题目大意

思路

简单树上dp

代码说明

代码

CPP

python

Java

Go

Js

Information

Status

Development

Support