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

题目描述

小红正在学习一套复杂软件系统的开发技能。共有 N 个技能模块，每个模块都有学习耗时、能力收益，以及至多一个直接前置模块。只有已经学习某个模块的直接前置模块时，才能继续学习该模块。
小红共有 T 小时。她可以学习任意多个满足前置关系的模块，每个模块至多学习一次。请计算在总耗时不超过 T 的条件下，她能够获得的最大能力收益之和。

输入输出

输入描述
第一行输入两个整数 N,T 。
接下来 N 行描述技能模块。每行先输入四个整数 id,time,power,k ，分别表示模块编号、学习耗时、能力收益和直接前置模块数量。
如果 k=1 ，该行末尾还会输入一个整数 parent ，表示直接前置模块编号；如果 k=0 ，该模块没有前置要求。
保证 1 ≤ N ≤ 100 ， 1 ≤ T ≤ 1000 ， 1 ≤ time ≤ 100 ， 1 ≤ power ≤ 1000 ， 0 ≤ k ≤ 1 。所有依赖关系不形成环。
输出描述
输出一个整数，表示小红能够获得的最大能力收益。如果无法学习任何模块，则输出 0 。

样例共 1 组

样例 1 · 学习模块 1 、模块 2 和模块 4 共消耗 7 小时，能力收益为 40 。
输入
5 7
1 2 10 0
2 3 18 1 1
3 4 25 1 1
4 2 12 0
5 1 8 1 4
输出
40

算法解析依据充分

考点：动态规划

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

题目画像

  • 数据规模：T ≤ 1e3，N ≤ 100
  • 元素值域：power ≤ 1e3，time ≤ 100（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：动态规划

本题切入点

带前置依赖的 0/1 背包（树形背包）：依赖关系构成森林，对每棵子树做 dp[耗时] = 最大收益再向父节点合并；N≤100、T≤1000 规模可直接递推。

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 N ≤ 100，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 元素值域最大到 1e3 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 5 7 / 1 2 10 0 / 2 3 18 1 1 / 3 4 25 1 1 / 4 2 12 0 / 5 1 8 1 4 → 输出 40

学习模块 1 、模块 2 和模块 4 共消耗 7 小时，能力收益为 40 。

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

本题来源：2026年-华为-05月20号开发岗。

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