20260923-自由摄影师的最大收益（N0078）- 算法机考高频题型 · 华为OD / DP题解 | AlgoMooc

N0078. 20260923-自由摄影师的最大收益

困难

通过率 38% · 提交 16 · 通过 6

华为ODDP背包问题

概念速查：动态规划是什么

改编自算法机考高频题型 · 华为OD / DP类型 · 难度：困难

小华是一名自由职业摄影师，他接到了 N 个拍摄订单。每个订单 i 具有以下属性：

耗时 times[i]：完成该订单需要连续工作的天数。
截止日期 deadlines[i]：该订单必须在第 deadlines[i] 天或之前完成。
报酬 profits[i]：完成该订单获得的收益。小华从第 1 天开始工作，工作规则如下：
一旦开始某个订单，必须连续工作 times[i] 天，中间不能中断或切换其他订单，订单不能只部分完成。
每天小华只能处理一个订单，不能并行处理多个订单。例如：第 1 个订单从第 1 天开始处理，耗时 3 天，那么第 2 个订单只能在第 4 天开始安排。
对于选中的订单 i，其完成时间必须在 deadlines[i] 之前，即：起始时间 + times[i] - 1 <= deadlines[i]。例如一个耗时 3 天、截止日期在第 7 天的订单，从第 5 天开始处理，满足 5 + 3 - 1 <= 7，符合截止时间要求。小华希望选择一组订单并安排它们的执行顺序，使得总报酬最大，同时满足所有选中订单的截止时间和互斥约束。

这类题属于算法机考高频题型中「华为OD / DP」方向的高频题型，通常考察对「华为OD / DP」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

包含 3 个长度相同的数组，长度即订单数量 N（1 <= N <= 500），数组定义如下：

times：表示每个订单需要的耗时（天），1 <= times[i] <= 10^3。
deadlines：表示每个订单的截止日期，1 <= deadlines[i] <= 10^3。
profits：表示每个订单对应的报酬，1 <= profits[i] <= 10^3。

输出描述

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

示例

示例 1

输入示例

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

输出示例

说明：

共有 4 个订单：

订单 A：耗时 3 天，截止日期 3，报酬 100
订单 B：耗时 1 天，截止日期 2，报酬 40
订单 C：耗时 1 天，截止日期 3，报酬 40
订单 D：耗时 1 天，截止日期 3，报酬 40 如果小华贪图高报酬选择订单 A，他需要从第 1 天工作到第 3 天，刚好在第 3 天交付。但这期间他无法再做其他任何订单，总收益为 100。最优策略是放弃订单 A，依次完成订单 B、C、D：
第 1 天：完成订单 B（满足截止日期 2），获得 40。
第 2 天：完成订单 C（满足截止日期 3），获得 40。
第 3 天：完成订单 D（满足截止日期 3），获得 40。

最大总收益为 120。

示例 2

输入示例

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

输出示例

说明：

说明

订单 A：耗时 2 天，截止日期 2，报酬 50
订单 B：耗时 2 天，截止日期 3，报酬 100
订单 C：耗时 1 天，截止日期 2，报酬 60 如果小华这样安排：
第 1~2 天：完成订单 A，获得 50（刚好在第 2 天结束前完成）。
第 3~4 天：完成订单 B，获得 100。但是订单 B 需要耗时 2 天，从第 3 天开始，第 4 天才能结束，超过了截止日期 3。最优安排应是：
第 1 天：完成订单 C（耗时 1 天，满足截止日期 2），获得 60。
第 2~3 天：完成订单 B（耗时 2 天，第 2、3 天做，第 3 天结束，满足截止日期 3），获得 100。最大总收益为 160。

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

未登录也能直接「运行」调试;「提交」判题需微信登录,你写的代码会自动保留、登录后回到本题继续。

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List
from math import inf

class Solution:
    def maxProfit(self, times: List[int], deadlines: List[int], profits: List[int]) -> int:
        return 0

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写
if __name__ == "__main__":
    import sys
    input_lines = sys.stdin.read().strip().split('\n')
    
    n = int(input_lines[0])
    times = list(map(int, input_lines[1].split(',')))
    deadlines = list(map(int, input_lines[2].split(',')))
    profits = list(map(int, input_lines[3].split(',')))
    
    sol = Solution()
    print(sol.maxProfit(times, deadlines, profits))

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交