华为OD机试 - 获取最多食物 - 拓扑排序、动态规划(Python/JS/C/C++ 2024 E卷 200分)

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中,刷题点这里

专栏导读

本专栏收录于《华为OD机试真题(Python/JS/C/C++)》。

刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。

一、题目描述

主办方设计了一个获取食物的游戏。

游戏的地图由 N×N×N 个方格组成,每个方格上至多 222 个传送门,通过传送门可将参与者传送至指定的某些方格。同时,每个方格上标注了三个数字:

  1. 第一个数字为 id idd: 代表方格的编号,从 000 到 N×N×N−1,每个方格各不相同;
  2. 第二个数字为 parent-id parent-id parent-id:代表从编号为 parent-id parent-id parent-id 的方格可以通过传送门传送到当前方格(-1-1-1 则表示没有任何方格可以通过传送门传送到此方格,这样的方格在地图中只有一个);
  3. 第三个数字为 value value value:取值在 [100,100] | [100,100] | [100,100] 的整数值,正整数代表参与者得到相应数值的食物,负数代表失去相应数值的食物(当某个方格有负数的情况时,000 则代表无变化)。

此外,地图设计时保证了参与者不可能通过传送门形成环次,并且至少有一个方格的 value 是正整数。

游戏结束时,参与者从任意选择一个方格为出发点,当遇到下列情况之一退出游戏:

  • 参与者踏出地图的方格后传送门;
  • 参与者在任意方格上主动宣布退出游戏。

请计算参与者退出游戏后,最多可以获得多少单位的食物。

二、输入描述

第一行,方块个数 N

接下来输入 N 行 (id < N parent-id < N),每行记录了相应方格上标注的3个数字,即 id (0 <= id < 10000)、parent-id (0 <= parent-id < 10000) 和 value (-100 <= value <= 100)

特殊的 parent-id 可以取 -1,则表示没有任何方格可以通过传送门传送到此方格,这样的方格在地图中有且仅有一个。

三、输出描述

输出为一个整数,表示参与者退出游戏后最多可以获得多少单位的食物。

四、测试用例

测试用例1:

1、输入

7
0 1 8
1 -1 -2
2 1 9
4 0 -2
5 4 3
3 0 -3
6 2 -3

2、输出

9

3、说明

参与者从方格 000 出发,通过传送门到达方格 444,再通过传送门到达方格 555。一共获得 8 + (-2) + 3 = 9。8+(-2)+3=9 单位食物,得到食物最多。

或者参与者在游戏开始时处于方格 222,直接主动宣布退出游戏,也可以获得 999 个单位食物。

测试用例2:

1、输入

3
0 -1 3
1 0 1
2 0 2

2、输出

5

3、说明

参与者从方格 000 出发,通过传送门到达方格 222,一共可以获得 3 + 2 = 5。3 + 2 = 5 个单位食物,此时得到食物最多。

五、解题思路

本题涉及在一个无环图(DAG)中寻找路径,使得路径上节点的数值之和最大。具体来说,参与者可以从任意一个方格出发,沿着传送门移动,最终选择退出游戏。目标是找到这样一条路径,使得路径上所有方格的数值之和最大。

1、数据结构与算法

图的表示:使用邻接表(List<List>)来表示图,其中每个节点的列表存储其子节点(即可以通过传送门到达的方格)。

节点信息存储:使用数组或映射来存储每个节点的数值(value)。

拓扑排序:由于图是无环的,可以使用拓扑排序来遍历节点。

2、为什么选择这几个数据结构?

邻接表适用于表示稀疏图,且易于进行拓扑排序和遍历。

拓扑排序确保在处理每个节点时,其所有的父节点已经被处理,便于进行动态规划。

动态规划能够高效地计算出每个节点的最大路径和,最终求得全局最大值。

3、主要步骤:

  1. 输入解析:读取所有方格的信息,包括 id、parent-id 和 value。
  2. 图构建:根据 parent-id 构建图的邻接表。每个 parent-id 指向其子节点 id。
  3. 拓扑排序:计算每个节点的入度,使用队列进行拓扑排序,确保节点按依赖顺序处理。
  4. 动态规划:
    • 初始化每个节点的最大食物数为其自身的 value。
    • 按拓扑顺序遍历每个节点,更新其子节点的最大食物数为 当前节点的最大食物数 + 子节点的 value(如果更大)。
  5. 结果计算:遍历所有节点的最大食物数,找出其中的最大值即为最终结果。

4、关键点注意

无环保证:题目保证了图中不存在环,这使得拓扑排序成为可行的方案。

多起点:参与者可以从任意节点出发,因此需要初始化每个节点的最大食物数为其自身的 value。

负数处理:路径上的某些节点可能会减少总食物数,但由于参与者可以选择随时退出,因此路径的最大和可能不包括所有节点。

六、Python算法源码

# 导入所需的模块
import sys
from collections import dequedef main():# 读取所有输入并按行分割input_lines = sys.stdin.read().splitlines()# 如果没有输入,直接返回if not input_lines:print(0)return# 读取方块个数 NN = int(input_lines[0].strip())# 初始化数组存储每个节点的 value,假设 id 范围为 0 到 9999values = [0] * 10000# 初始化邻接表,存储每个节点的子节点graph = [[] for _ in range(10000)]# 初始化集合记录所有节点的 idnodeIds = set()# 初始化数组记录每个节点的入度inDegree = [0] * 10000# 逐行读取 N 行方块信息for i in range(1, N + 1):parts = input_lines[i].strip().split()id = int(parts[0])           # 方块编号parentId = int(parts[1])     # 父方块编号value = int(parts[2])        # 方块的 valuevalues[id] = value            # 存储方块的 valuenodeIds.add(id)              # 记录方块的 id# 如果 parentId 不为 -1,构建图的边并更新入度if parentId != -1:graph[parentId].append(id)  # parentId 指向 idinDegree[id] += 1           # 增加 id 的入度# 初始化队列用于拓扑排序queue = deque()# 初始化最大食物数数组,每个节点的初始最大食物数为其自身的 valuemaxFood = [0] * 10000for id in nodeIds:maxFood[id] = values[id]               # 设置初始值if inDegree[id] == 0:queue.append(id)                   # 入度为 0 的节点入队# 初始化全局最大食物数为最小可能值globalMax = -float('inf')# 进行拓扑排序并计算最大食物数while queue:current = queue.popleft()              # 获取当前节点if maxFood[current] > globalMax:globalMax = maxFood[current]        # 更新全局最大食物数# 遍历当前节点的所有子节点for child in graph[current]:# 如果通过当前节点到子节点的路径更优,更新子节点的最大食物数if maxFood[current] + values[child] > maxFood[child]:maxFood[child] = maxFood[current] + values[child]inDegree[child] -= 1                # 减少子节点的入度if inDegree[child] == 0:queue.append(child)              # 入度为 0 的子节点入队# 输出全局最大食物数print(globalMax)# 调用主函数
if __name__ == "__main__":main()

七、JavaScript算法源码

// 使用 Node.js 的 readline 模块读取标准输入
const readline = require('readline');// 创建接口实例
const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false
});let inputLines = []; // 存储输入的每一行// 监听每一行输入
rl.on('line', function(line){inputLines.push(line.trim()); // 去除首尾空白并存储
}).on('close', function(){// 如果没有输入,输出 0 并退出if(inputLines.length === 0){console.log(0);return;}// 读取方块个数 Nconst N = parseInt(inputLines[0]);// 初始化数组存储每个节点的 value,假设 id 范围为 0 到 9999const values = Array(10000).fill(0);// 初始化邻接表,存储每个节点的子节点const graph = Array.from({length: 10000}, () => []);// 初始化集合记录所有节点的 idconst nodeIds = new Set();// 初始化数组记录每个节点的入度const inDegree = Array(10000).fill(0);// 逐行读取 N 行方块信息for(let i = 1; i <= N; i++){const parts = inputLines[i].split(/\s+/);const id = parseInt(parts[0]);        // 方块编号const parentId = parseInt(parts[1]);  // 父方块编号const value = parseInt(parts[2]);     // 方块的 valuevalues[id] = value;                    // 存储方块的 valuenodeIds.add(id);                       // 记录方块的 id// 如果 parentId 不为 -1,构建图的边并更新入度if(parentId !== -1){graph[parentId].push(id);          // parentId 指向 idinDegree[id] += 1;                 // 增加 id 的入度}}// 初始化队列用于拓扑排序const queue = [];// 初始化最大食物数数组,每个节点的初始最大食物数为其自身的 valueconst maxFood = Array(10000).fill(0);nodeIds.forEach(id => {maxFood[id] = values[id];            // 设置初始值if(inDegree[id] === 0){queue.push(id);                   // 入度为 0 的节点入队}});// 初始化全局最大食物数为最小可能值let globalMax = -Infinity;// 进行拓扑排序并计算最大食物数while(queue.length > 0){const current = queue.shift();         // 获取当前节点if(maxFood[current] > globalMax){globalMax = maxFood[current];       // 更新全局最大食物数}// 遍历当前节点的所有子节点graph[current].forEach(child => {// 如果通过当前节点到子节点的路径更优,更新子节点的最大食物数if(maxFood[current] + values[child] > maxFood[child]){maxFood[child] = maxFood[current] + values[child];}inDegree[child] -= 1;             // 减少子节点的入度if(inDegree[child] === 0){queue.push(child);             // 入度为 0 的子节点入队}});}// 输出全局最大食物数console.log(globalMax);
});

八、C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>// 定义最大方块数量和最大ID
#define MAX_BLOCKS 10000
#define MAX_LINE_LENGTH 100int main(){int N;// 读取方块个数 Nif(scanf("%d", &N) != 1){// 如果读取失败,输出0并退出printf("0\n");return 0;}// 初始化数组存储每个节点的 value,假设 id 范围为 0 到 9999int values[MAX_BLOCKS];memset(values, 0, sizeof(values));// 初始化邻接表,使用二维数组存储每个节点的子节点int graph[MAX_BLOCKS][222]; // 每个节点最多有222个子节点int graphSize[MAX_BLOCKS];memset(graphSize, 0, sizeof(graphSize));// 初始化数组记录每个节点的入度int inDegree[MAX_BLOCKS];memset(inDegree, 0, sizeof(inDegree));// 初始化数组记录节点是否存在int exists[MAX_BLOCKS];memset(exists, 0, sizeof(exists));char line[MAX_LINE_LENGTH];// 逐行读取 N 行方块信息for(int i = 0; i < N; i++){if(scanf("%s", line) != 1){// 如果读取失败,跳过continue;}// 使用 sscanf 解析 id, parentId, valueint id, parentId, value;sscanf(line, "%d %d %d", &id, &parentId, &value);values[id] = value;          // 存储方块的 valueexists[id] = 1;              // 标记节点存在// 如果 parentId 不为 -1,构建图的边并更新入度if(parentId != -1){graph[parentId][graphSize[parentId]++] = id; // parentId 指向 idinDegree[id]++;                            // 增加 id 的入度}}// 初始化队列用于拓扑排序,使用数组模拟队列int queue[MAX_BLOCKS];int front = 0, rear = 0;// 初始化最大食物数数组,每个节点的初始最大食物数为其自身的 valueint maxFood[MAX_BLOCKS];for(int i = 0; i < MAX_BLOCKS; i++){if(exists[i]){maxFood[i] = values[i];     // 设置初始值if(inDegree[i] == 0){queue[rear++] = i;      // 入度为 0 的节点入队}}}// 初始化全局最大食物数为最小可能值int globalMax = -1000000; // 根据题目,最小可能为 -100 * N// 进行拓扑排序并计算最大食物数while(front < rear){int current = queue[front++]; // 获取当前节点if(maxFood[current] > globalMax){globalMax = maxFood[current]; // 更新全局最大食物数}// 遍历当前节点的所有子节点for(int i = 0; i < graphSize[current]; i++){int child = graph[current][i];// 如果通过当前节点到子节点的路径更优,更新子节点的最大食物数if(maxFood[current] + values[child] > maxFood[child]){maxFood[child] = maxFood[current] + values[child];}inDegree[child]--;           // 减少子节点的入度if(inDegree[child] == 0){queue[rear++] = child;   // 入度为 0 的子节点入队}}}// 输出全局最大食物数printf("%d\n", globalMax);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int N;// 读取方块个数 Ncin >> N;// 初始化数组存储每个节点的 value,假设 id 范围为 0 到 9999int values[10000];memset(values, 0, sizeof(values));// 初始化邻接表,存储每个节点的子节点vector<vector<int>> graph(10000, vector<int>());// 初始化数组记录每个节点的入度int inDegree[10000];memset(inDegree, 0, sizeof(inDegree));// 初始化数组记录节点是否存在bool exists[10000];memset(exists, false, sizeof(exists));// 逐行读取 N 行方块信息for(int i = 0; i < N; i++){int id, parentId, value;cin >> id >> parentId >> value;values[id] = value;          // 存储方块的 valueexists[id] = true;           // 标记节点存在// 如果 parentId 不为 -1,构建图的边并更新入度if(parentId != -1){graph[parentId].push_back(id); // parentId 指向 idinDegree[id]++;               // 增加 id 的入度}}// 初始化队列用于拓扑排序queue<int> q;// 初始化最大食物数数组,每个节点的初始最大食物数为其自身的 valueint maxFood[10000];for(int i = 0; i < 10000; i++){if(exists[i]){maxFood[i] = values[i];       // 设置初始值if(inDegree[i] == 0){q.push(i);                // 入度为 0 的节点入队}}}// 初始化全局最大食物数为最小可能值int globalMax = INT32_MIN;// 进行拓扑排序并计算最大食物数while(!q.empty()){int current = q.front(); q.pop(); // 获取当前节点if(maxFood[current] > globalMax){globalMax = maxFood[current];   // 更新全局最大食物数}// 遍历当前节点的所有子节点for(auto &child : graph[current]){// 如果通过当前节点到子节点的路径更优,更新子节点的最大食物数if(maxFood[current] + values[child] > maxFood[child]){maxFood[child] = maxFood[current] + values[child];}inDegree[child]--;             // 减少子节点的入度if(inDegree[child] == 0){q.push(child);             // 入度为 0 的子节点入队}}}// 输出全局最大食物数cout << globalMax << "\n";return 0;
}

🏆下一篇:华为OD机试真题 - 简易内存池(Python/JS/C/C++ 2024 E卷 200分)

🏆本文收录于,华为OD机试真题(Python/JS/C/C++)

刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1548381.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

计算机毕业设计 基于Python的广东旅游数据分析系统的设计与实现 Python+Django+Vue Python爬虫 附源码 讲解 文档

&#x1f34a;作者&#xff1a;计算机编程-吉哥 &#x1f34a;简介&#xff1a;专业从事JavaWeb程序开发&#xff0c;微信小程序开发&#xff0c;定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事&#xff0c;生活就是快乐的。 &#x1f34a;心愿&#xff1a;点…

职场基本功:情绪管理的行动指南(前置情绪管理)

文章目录 引言情绪管理的目标情绪产生的阶段前置情绪管理避免情绪失控的技巧案例分析引言 成熟的职场人,必备的五项技能: 管理自己的情绪:职场需要你的行为是可控的,只有情绪是稳定的,其他人才能顺利地跟你展开协作。称赞他人:赞赏能让你获得一个友好的交流环境求助他人…

为什么这款智能在线派单软件成为行业首选?

智能在线派单软件通过自动化任务分配等提升效率&#xff0c;ZohoDesk因其全方位服务管理、智能分配、定制性强、数据分析等功能&#xff0c;成为企业优选。实例涵盖物流、家政、维修、医疗等行业&#xff0c;提高效率和客户满意度。 一、智能在线派单软件有什么功能 在深入探讨…

GPT理论

1.GPT发展 Transformer是一个用作翻译任务的模型&#xff0c;谷歌出品。 GPT全称 lmproving Language Understanding by Generative Pre-Training&#xff0c;用预训练语言理解模型。OPENAI出品。 BERT全称Pre-training of Deep BidirectionalTransformers for Language Unde…

C++入门day5-面向对象编程(终)

C入门day4-面向对象编程&#xff08;下&#xff09;-CSDN博客 本节是我们面向对象内容的最终篇章&#xff0c;不是说我们的C就学到这里。如果有一些面向对象的基础知识没有讲到&#xff0c;后面会发布在知识点补充专栏&#xff0c;全都是干货满满的。 https://blog.csdn.net/u…

阿博图书馆管理:SpringBoot实战指南

第二章 开发技术介绍此次B/S结构、Java技术以及mysql数据库是该阿博图书馆管理系统的主要开发技术&#xff0c;然后对系统的整体设计、数据库设计、功能模块设计、系统页面设计以及系统程序设计进行了详细的研究与规划。 2.1 系统开发平台 在该阿博图书馆管理系统中&#xff0c…

OJ在线评测系统 代码沙箱优化模版方法模式 使用与有规范的流程 并且执行流程可以复用

代码沙箱优化模版方法模式 上次我们代码沙箱的docker实现和原生实现 我们可以使用模版方法设计模式去优化我们的代码 我们原生的java实现代码沙箱和docker实现代码沙箱是有更多重复点的 比如说把文件 收集文件 进行校验 我们要用模版方法设计模式 定义一套通用的执行流程 让…

2024年合肥市职业院校技能大赛(中职组)赛 网络安全理论题

竞赛内容 模块A: 理论技能与职业素养 培训、环境、资料、考证 公众号&#xff1a;Geek极安云科 网络安全群&#xff1a;624032112 网络系统管理群&#xff1a;223627079 网络建设与运维群&#xff1a;870959784 极安云科专注于技能提升&#xff0c;赋能 2024年广东省高校的技…

cubemx配置ADC

参考博客&#xff1a;https://blog.csdn.net/qq_29031103/article/details/119894077 生成代码&#xff1b; 接着编写代码&#xff1a; 1&#xff09;在main函数bsp初始化部分&#xff1b; 添加&#xff1a;HAL_ADCEx_Calibration_Start(&hadc1); 2&#xff09;在…

C++之STL—常用拷贝和替换算法

copy(iterator beg, iterator end, iterator dest); // 按值查找元素&#xff0c;找到返回指定位置迭代器&#xff0c;找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // dest 目标起始迭代器 replace(iterator beg, iterator end, oldvalue, newvalue); …

Techub专访顾荣辉教授:解密CertiK的安全战略路线

当 Web3 安全审计公司还在争抢审计份额时&#xff0c;CertiK 已经开始将目光瞄准即将进军 Web3 的传统商业巨头。CertiK 不仅在传统行业进行白帽行动获得如苹果公司的官方感谢&#xff0c;还是 Web3 行业唯一一家拥有 SOC 2 和 ISO 认证的 Web3 的安全公司。基于此&#xff0c;…

Redis篇(数据类型)

目录 讲解一&#xff1a;简介 讲解二&#xff1a;常用 一、String类型 1. 简介 2. 常见命令 3. Key结构 4. 操作String 5. 实例 二、Hash类型 1. 简介 2. 常见命令 3. 3操作hash 4. 实例 三、List类型 1. 简介 2. 特征 3. 应用场景 4. 常见命令 5. 操作list …

AT89C51 利用SBIT寻址,并且在内存中实现伪动态密码的混淆

前置发现 && 分析 char bdata DB[2]; //char sbit x bdata DB[0]^7; //取内存地址数组[0]地址的的七位 这样我们可以对数组DB中索引0的位置进行修改… 例如,将密码A映射到真实密码C,这样做的好处是你的程序被逆向分析的时候,攻击者无法真正知道密码到底是什么…因为…

程序员必备秘籍:掌握代码规范,让开发效率飞速提升!

在软件开发的世界里&#xff0c;代码规范如同指南针&#xff0c;为开发团队和测试团队指明方向。一个统一的代码规范不仅能够提升代码的可读性和可维护性&#xff0c;还能显著提高开发效率和团队协作能力。 本文将带你深入了解代码规范的重要性&#xff0c;并揭示如何通过它来实…

Angular与Vue的全方位对比分析

一、框架概述 Angular Angular是由Google开发和维护的一款开源JavaScript框架。它采用TypeScript编写&#xff0c;具有一套完整的开发工具和规范。Angular遵循MVC&#xff08;Model - View - Controller&#xff09;或更确切地说是MVVM&#xff08;Model - View - ViewModel&a…

探索私有化聊天软件:即时通讯与音视频技术的结合

在数字化转型的浪潮中&#xff0c;企业对于高效、安全、定制化的通讯解决方案的需求日益迫切。鲸信&#xff0c;作为音视频通信技术的佼佼者&#xff0c;凭借其强大的即时通讯与音视频SDK&#xff08;软件开发工具包&#xff09;结合能力&#xff0c;为企业量身打造了私有化聊天…

原生代理IP是什么?

代理IP的各个类型称呼有很多&#xff0c;且它们在网络使用和隐私保护方面扮演着不同的角色。今天将探讨什么是原生IP以及原生IP和住宅IP之间的区别&#xff0c;帮助大家更好地理解这两者的概念和实际应用&#xff0c;并选择适合自己的IP类型。 一、什么是原生IP&#xff1f; 原…

【Transformers实战篇2】练习之命名实体识别

文章目录 一、命名实体识别简介1.1 数据标注体系1.2 IOB2标注体系1.3 IOBES标注体系 二、代码实战2.1 导入相关包2.2 加载数据集2.3 数据集预处理2.3.1 借助word_idx实现标签映射 2.4 创建模型2.5 创建评估函数2.6 配置训练参数2.7 创建训练器2.8 模型训练2.9 模型预测 本文为 …

基于SSM的图书管理管理系统的设计与实现 (含源码+sql+视频导入教程)

&#x1f449;文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1 、功能描述 基于SSM的图书管理管理系统4拥有两种角色&#xff0c;用户可以浏览评论图书、登录注册&#xff0c;管理员可以进行图书馆管理、用户管理、分类管理等功能 1.1 背景描述 图书书店销售管理…

Apache OFBiz SSRF漏洞CVE-2024-45507分析

Apache OFBiz介绍 Apache OFBiz 是一个功能丰富的开源电子商务平台&#xff0c;包含完整的商业解决方案&#xff0c;适用于多种行业。它提供了一套全面的服务&#xff0c;包括客户关系管理&#xff08;CRM&#xff09;、企业资源规划&#xff08;ERP&#xff09;、订单管理、产…