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

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

题目描述

云南的菌子加工厂要加工一批野生菌，所有菌子同时进厂。由于菌子新鲜度随时间流失，价值不断衰减。工厂不能同时加工菌子，即逐个串行加工，正在加工的菌子价值不再衰减，加工完毕立即售卖。

已知每个菌子的初始市场价值和新鲜度衰减速度（每小时损失的价值），菌子的实际价值 = 初始价值 - 衰减速度 × 从进入工厂到开始加工的等待时间。在给定时间内，合理安排加工顺序使得加工完成的菌子总价值最大化。

每个菌子的加工时间固定为 5 小时，加工所有菌子的总耗时不能超过给定的总加工时间。若菌子的实际价值衰减至零或负值，则不能再售卖，即不需要参与加工。

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

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

输入描述

输入为四行：

count
total
values
decays

• count 表示菌子数量，1 <= count <= 15
• total 表示可用总加工时间，5 <= total <= 75，单位小时
• values[i] 表示第 i 个菌子的初始市场价值
• decays[i] 表示第 i 个菌子的衰减速度

数组 values 和 decays 按示例使用英文逗号分隔。

输出描述

输出一个整数，表示在给定时间内能加工完成的菌子的最大总价值。

示例1

输入

3
15
10,8,6
0,0,0

输出

24

示例2

输入

3
20
20,10,15
3,1,2

输出

25

解题思路

核心思想

count <= 15，可以用二进制状态 mask 表示已经加工过的菌子集合。若 mask 中有 cnt 个菌子，则下一个菌子的开始加工时间为 cnt * 5。枚举下一个可加工且当前价值仍为正的菌子，更新新状态的最大收益。

算法步骤

1. 最多能加工 total / 5 个菌子。
2. 定义 dp[mask] 表示已经加工集合为 mask 时可获得的最大总价值。
3. 初始 dp[0] = 0。
4. 枚举所有状态：
   • 计算已经加工数量 cnt 和当前等待时间 cnt * 5；
   • 若已经达到最大加工数量，则不能继续扩展；
   • 枚举未加工菌子，若当前实际价值为正，则转移到新状态。
5. 所有状态中的最大收益即为答案。

复杂度分析

设菌子数量为 n。

• 时间复杂度：O(n * 2^n)。
• 空间复杂度：`O(2^