小红正在尝试训练一个超大规模的语言模型,但由于显存有限,训练过程中出现了空间不足的问题。为了让程序继续运行,小红必须从当前的 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。
6 3 3 3 5 10 2 5 1 8 10
3
考点:动态规划
数据规模 n ≤ 1e4 | 限制 3 秒 / 512MB | 标准输入输出
推荐方向:动态规划
本题切入点
每个张量的成本取 min(交换, 重算),问题变成「选若干物品使空间之和 ≥m 且成本最小」:用背包 DP(dp[已释放空间] = 最小成本,容量截到 m),凑不出则 error。
把问题拆成子问题,用状态表示「已处理到哪儿」,靠转移方程递推。
思路框架(动态规划 通法 · 非本题专属)
实现要点:一般是「先枚举阶段,再枚举状态,最后枚举决策」三层循环;空间大时可滚动数组优化。
复杂度:时间 O(状态数 × 转移代价) | 空间 O(状态数)
该范式的通法易错点
对照本题
样例 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岗。