2 solutions

  • 0
    @ 2024-9-26 22:49:38

    !!!!我终于写对了一次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;
}
    • 0
      @ 2024-8-21 3:41:18

      题目大意

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

      思路

      简单树上dp

      1.数据结构设计：

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

      2.输入处理：

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

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

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

      4.结果输出：

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

      时间复杂度：O(N)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(); // 调用主程序
      • 1

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

      Information

      ID
      5
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      7
      Tags
      # Submissions
      127
      Accepted
      31
      Uploaded By
      1. About
      2. Contact Us
      3. Privacy
      4. Terms of Service
      5. Copyright Complaint
      6. Language
      7. Legacy mode
      8. Theme
      2. 湘ICP备2023007293号
      3. Worker 0, 24ms
      4. Powered by Hydro v4.14.1 Community