华为 · 动态规划 · 算法编程题
华为 动态规划 n ≤ 100 时限 3 秒 / 256 MB

题目描述

一名星际探险家正在规划一次勘探任务。已知宇宙中有 n 个未探索的星球，探险家的飞船总共有 T 单位的续航时间和 H 单位的能量储备。
对于第 i 个星球，进行勘探需要花费 t_i 的续航时间、消耗 h_i 的能量，并能够获得价值为 a_i 的科学数据。
请问，在总续航时间不超过 T 、总能量消耗不超过 H 的前提下，探险家最多可以获得多少总价值的科学数据？
数据范围提示： 1 ≤ n ≤ 100 ，其他所有输入数值均为正整数。

输入输出

输入描述
第一行输入一个正整数 n ，代表待勘探星球的数量。
第二行输入两个正整数 T 和 H ，分别代表续航时间上限和能量储备上限。
接下来的 n 行，每行输入三个正整数 t_i, h_i, a_i ，分别代表勘探第 i 个星球所需的时间、消耗的能量以及能获得的科学数据价值。
输出描述
输出一个整数，代表能够获得的最大科学数据总价值。

样例共 1 组

样例 1
输入
9
35 35
5 1 22
4 2 11
3 9 48
2 3 22
1 4 41
5 2 38
9 4 96
8 1 98
7 8 62
输出
405

算法解析依据充分

考点：动态规划

数据规模 n ≤ 100 ｜ 限制 3 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 100
  • 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：动态规划

本题切入点

二维费用 0/1 背包：dp[t][h] = 最大科学数据价值，每颗星球枚举「勘探/不勘探」两种转移；n≤100 时二维递推规模可控。

把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。

思路框架（动态规划 通法 · 非本题专属）

  1. 定义状态：dp[i] / dp[i][j] 表示什么（这是最关键的一步，状态定义错就全错）。
  2. 写转移方程：当前状态由哪些更小的状态推来。
  3. 确定初始条件与遍历顺序（保证用到的状态已算好）。
  4. 确定答案取哪个状态；数值大时全程取模。

实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。

复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)

该范式的通法易错点

  • 状态定义不完整（漏了必要维度），导致子问题之间有后效性。
  • 初始化写错（尤其「恰好」与「至多」的初值差别）。
  • 遍历顺序与依赖方向不一致。

对照本题

  • 数据规模 n ≤ 100，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。

题目给出的提示

  • 1 ≤ n ≤ 100 ，其他所有输入数值均为正整数

样例

样例 1

  • 输入：9 / 35 35 / 5 1 22 / 4 2 11 / 3 9 48 / 2 3 22 / 1 4 41 / 5 2 38 / 9 4 96 / 8 1 98 / 7 8 62
  • 输出：405

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-10月22号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解