2026 华为OD机试真题 6月7日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

某部门的项目经理，近期手头有 n 个开发任务必须全部完成（不可并行，必须顺序执行）。每个任务 i 有三个属性：

• 持续时间 duration[i]：执行该任务需要的时间；
• 截止时间 deadline[i]：任务必须在某个时刻前完成才能获得收益；
• 收益 profit[i]：若在截止时间前完成，可获得的收益。

任务从时刻 0 开始依次执行。若任务 i 的完成时刻（即开始时刻 + duration[i]）≤deadline[i]，则你获得 profit[i]；否则该任务收益为 0（任务仍要执行）。他可以任意决定任务的执行顺序，目标是最大化所有任务的总收益。请帮他计算最大可能收益。

2026 华为OD机试真题 6月7日华为OD上机新系统考试真题 200 分题型

输入描述

共有 4 个输入参数：

1. n：任务数量（1≤n≤20），编号 0 到 n-1。
2. duration：长度为 n 的正整数数组，duration[i]≤1000。
3. deadline：长度为 n 的正整数数组，deadline[i]≤1000。
4. profit：长度为 n 的正整数数组，profit[i]≤1000。

输出描述

输出一个整数，表示能获得的最大总收益。

示例1

输入

3,[2,1,3],[3,2,5],[10,20,30]

输出

50

说明

说明

按顺序任务 2 → 任务 3 → 任务 1 执行：

• 任务 2：时刻 0 开始，持续 1，完成于时刻 1 ≤ 2，收益 20；
• 任务 3：时刻 1开始，持续 3，完成于时刻 4 ≤ 5，收益 30；
• 任务 1：时刻 4 开始，持续 2，完成于时刻 6 > 3，收益 0。 总收益 = 20+30+0=50，此为最大。

示例2

输入

4,[1,2,3,4],[1,3,6,10],[100,200,300,400]

输出

1000

说明

说明

所有任务按原顺序执行均可满足截止时间，总收益为 100+200+300+400=1000。

示例3

输入

2,[5,5],[4,10],[100,200]

输出

200

说明

说明

• 第一个任务持续时间 5，截止时间 4，无论如何排序都会超时，收益为 0。
• 第二个任务无论何时执行均可在截止前完成，收益 200。 故最大收益为 200。

解题思路

本题是一个 任务调度优化 问题，要求在任务必须顺序执行的前提下，通过选择最优执行顺序来最大化总收益。

状态压缩 DP 思路：

• 使用二进制 mask 表示已完成的任务集合
• dp[mask] = (最大收益, 达成该收益的最小完成时刻)
• 对于每个状态，枚举最后执行的任务 j，计算新的收益和时间
• 若 完成时刻 <= 截止时间，则获得对应收益；否则收益为 0
• 状态转移时优先选择收益更大的方案，收益相同时选择完成时刻更小的

关键点：

• n ≤ 20，使用 2^n 状态压缩 DP
• 每个状态需要记录（收益, 完成时刻）两个值
• 收益相同时保留最小完成时刻，确保后续任务有更多时间

复杂度分析

• 时间复杂度：O(n² × 2^n)，枚举所有状态及转移
• 空间复杂度：O(2^n)，存