2026 华为OD机试真题9月23日华为OD上机新系统考试真题 100 分题型

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

题目描述

小华是一名自由职业摄影师，他接到了 N 个拍摄订单。每个订单 i 包含完成订单需要连续工作的天数 times[i]、必须完成订单的截止日期 deadlines[i]，以及完成订单可以获得的收益 profits[i]。

小华从第 1 天开始工作。一旦开始某个订单，就必须连续完成，中间不能暂停或切换其他订单；每天只能处理一个订单，所有被选择订单的完成时间都不能超过各自的截止日期。

小华可以放弃任意订单，请计算在满足所有截止日期和互斥约束的情况下能够获得的最大总收益。

2026 华为OD机试真题9月23日华为OD上机新系统考试真题 100 分题型

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

输入描述

第一行输入由英文逗号分隔的整数数组 times，表示每个订单需要的工作天数。

第二行输入由英文逗号分隔的整数数组 deadlines，表示每个订单的截止日期。

第三行输入由英文逗号分隔的整数数组 profits，表示每个订单的收益。三个数组长度相同，订单数量满足 1 ≤ N ≤ 500，数组元素均为正整数。

输出描述

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

示例1

输入

3,1,1,1
3,2,3,3
100,40,40,40

输出

120

说明

选择耗时为 3 天的订单只能获得 100 收益；选择后三个耗时均为 1 天的订单，可以在各自截止日期前完成并获得 40+40+40=120 收益，因此最大收益为 120。

示例2

输入

2,2,1
2,3,2
50,100,60

输出

160

说明

先完成耗时 1 天、截止日期为第 2 天的订单，再完成耗时 2 天、截止日期为第 3 天的订单，可以获得 60+100=160 的最大收益。

解题思路

本题采用【排序 + 0/1 背包动态规划】算法：对于任意一组可行订单，都可以按照截止日期从小到大执行而不破坏可行性，因此先将订单按截止日期升序排列。

使用 dp[day] 表示已经处理当前范围内的订单后，在总工作时间不超过 day 的情况下能够获得的最大收益。处理一个耗时为 duration、截止日期为 deadline 的订单时，完成时间最多为 deadline，因此从该上限开始倒序枚举时间，并使用 dp[day-duration]+profit 更新收益。倒序更新可以保证每个订单最多选择一次。

时间维度只需要开到最大截止日期与全部订单总耗时的较小值。所有订单处理完成后，dp 数组中的最大值就是答案；耗时超过自身截止日期的订单不会进入任何有