华为 · 动态规划 · 算法编程题
华为 动态规划 n ≤ 1e4 时限 3 秒 / 512 MB

题目描述

小红正在尝试训练一个超大规模的语言模型,但由于显存有限,训练过程中出现了空间不足的问题。为了让程序继续运行,小红必须从当前的 n 个候选项中挑选出一部分张量进行清理,以释放至少 m 单位的显存空间。
对于每一个张量,小红有两种处理方式:第一种是将其临时交换到系统内存中,第二种是直接将其删除并在未来需要时重新计算。这两种方式各自对应一个成本值。小红非常聪明,对于每一个被决定清理的张量,她都会从这两种方式中选择成本更低的一种来执行。
请你帮小红计算一下,在保证释放的空间总量不少于 m 的前提下,清理这些张量所需要的最小总成本是多少?

输入输出

输入描述
第一行包含一个整数 m(0 < m < 10000),表示小红需要释放的最少存储空间。
第二行包含一个整数 n(0 < n < 10000),表示候选张量的数量。
第三行包含 n 个整数,表示每个张量所占据的空间大小,数值均在 [1, 10^5] 范围内。
第四行包含 n 个整数,表示每个张量执行“交换”操作的成本,数值均在 [1, 10^5] 范围内。
第五行包含 n 个整数,表示每个张量执行“重算”操作的成本,数值均在 [1, 10^5] 范围内。
输出描述
输出一行,包含一个整数,代表满足要求的最小总成本。如果无论如何挑选都无法腾出至少 m 的空间,请输出字符串 error。

样例共 1 组

样例 1 · 在该样例中,小红需要释放至少 6 单位空间: 张量 1:空间为 3,交换成本 10,重算成本 1。小红会选择较低的成本 1。 张量 2:空间为 3,交换成本 2,重算成本 8。小红会选择较低的成本 2。 张量 3:空间为 5,交换成本 5,重算成本 10。小红会选择较低的成本 5。 如果选择清理张量 1 和张量 2,总释放空间为 3+3=6,刚好满足要求,此时总成本为 1+2=3。这是所有方案中成本最低的。
输入
6
3
3 3 5
10 2 5
1 8 10
输出
3

算法解析依据充分

考点:动态规划

数据规模 n ≤ 1e4 | 限制 3 秒 / 512MB | 标准输入输出

题目画像

  • 数据规模:m ≤ 1e4,n ≤ 1e4
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:3 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:动态规划

本题切入点

每个张量的成本取 min(交换, 重算),问题变成「选若干物品使空间之和 ≥m 且成本最小」:用背包 DP(dp[已释放空间] = 最小成本,容量截到 m),凑不出则 error。

把问题拆成子问题,用状态表示「已处理到哪儿」,靠转移方程递推。

思路框架(动态规划 通法 · 非本题专属)

  1. 定义状态:dp[i] / dp[i][j] 表示什么(这是最关键的一步,状态定义错就全错)。
  2. 写转移方程:当前状态由哪些更小的状态推来。
  3. 确定初始条件与遍历顺序(保证用到的状态已算好)。
  4. 确定答案取哪个状态;数值大时全程取模。

实现要点:一般是「先枚举阶段,再枚举状态,最后枚举决策」三层循环;空间大时可滚动数组优化。

复杂度:时间 O(状态数 × 转移代价) | 空间 O(状态数)

该范式的通法易错点

  • 状态定义不完整(漏了必要维度),导致子问题之间有后效性。
  • 初始化写错(尤其「恰好」与「至多」的初值差别)。
  • 遍历顺序与依赖方向不一致。

对照本题

  • 数据规模 n ≤ 1e4,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。

样例解读

样例 1:输入 6 / 3 / 3 3 5 / 10 2 5 / 1 8 10 → 输出 3

在该样例中,小红需要释放至少 6 单位空间:

张量 1:空间为 3,交换成本 10,重算成本 1。小红会选择较低的成本 1。

张量 2:空间为 3,交换成本 2,重算成本 8。小红会选择较低的成本 2。

张量 3:空间为 5,交换成本 5,重算成本 10。小红会选择较低的成本 5。

如果选择清理张量 1 和张量 2,总释放空间为 3+3=6,刚好满足要求,此时总成本为 1+2=3。这是所有方案中成本最低的。

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

本题来源:2026年-华为-03月14号AI岗。

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