华为 · dfs · 算法编程题
华为 dfs n ≤ 8 时限 1 秒 / 256 MB

题目描述

小红需要在若干计算卡上调度一组不可抢占任务。每个任务给定必须同时占用的计算卡集合、持续时间，以及至多一个前驱任务。
同一张卡在同一时刻只能被一个任务占用；有前驱的任务只能在前驱完成后开始。多个互不冲突的任务可以同时运行。求完成全部任务的最短时间。

输入输出

输入描述
第一行输入计算卡数量 p 和任务数量 n 。
随后每个任务按编号 0 到 n-1 输入三行：第一行是该任务需要占用的卡编号列表；第二行是正整数持续时间；第三行是前驱任务编号，无前驱时为 -1 。
保证 1 ≤ p ≤ 10 ， 1 ≤ n ≤ 8 ， 1 ≤ duration ≤ 10^9 ；每个卡列表非空且不重复；依赖图无环。
输出描述
输出完成全部任务的最短时间。

样例共 2 组

样例 1 · 先在卡 0 执行任务 1，随后任务 0 与依赖任务 1 的任务 2 可以并行。
输入
2 3
0
3
-1
0
2
-1
1
4
1
输出
6
样例 2 · 任务 1 必须等待任务 0 完成。
输入
3 2
0 1
4
-1
1 2
5
0
输出
9

算法解析依据充分

考点：dfs

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

题目画像

  • 数据规模：n ≤ 8
  • 元素值域：duration ≤ 1e9，p ≤ 10（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：dfs

本题切入点

任务数 n≤8 极小，直接 DFS 枚举任务执行顺序并模拟卡占用（记录每张卡的空闲时刻），满足前驱约束才可开始，取所有可行顺序中的最短完成时间。

一条路走到底再回溯，适合枚举全部方案与连通性判定。

思路框架（dfs 通法 · 非本题专属）

  1. 定义递归函数（当前状态、已选集合、累计答案）。
  2. 写终止条件，达到终止条件时结算答案。
  3. 枚举下一步的所有选择，做选择 → 递归 → 撤销选择（回溯）。
  4. 大规模的连通块统计可用 DFS/BFS 染色标记。

实现要点：回溯时务必把状态恢复干净；必要时加剪枝（可行性剪枝、最优性剪枝）。

复杂度：时间 O(状态数) ｜ 空间 O(递归深度)

该范式的通法易错点

  • 回溯时忘记撤销状态，答案被污染。
  • 没有剪枝导致指数级爆炸超时。

对照本题

  • 数据规模 n ≤ 8，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 2 3 / 0 / 3 / -1 / 0 / 2 / -1 / 1 / 4 / 1 → 输出 6

先在卡 0 执行任务 1，随后任务 0 与依赖任务 1 的任务 2 可以并行。

样例 2：输入 3 2 / 0 1 / 4 / -1 / 1 2 / 5 / 0 → 输出 9

任务 1 必须等待任务 0 完成。

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

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

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