华为 · 动态规划 · 算法编程题
华为 动态规划 N ≤ 50 时限 1 秒 / 256 MB

题目描述

小红正在优化一条由 N 个交换节点组成的数据通路，节点编号为 0 到 N-1 。数据包会依次经过所有节点，节点 i 默认产生 delay_i 单位时延。
如果在节点 i 启用优先转发，它会影响节点 i 本身以及后续至多 win_i 个节点。每个受影响节点的时延都会减少 opt_i ，但时延最低只能降到 0 。如果一个节点同时受到多个已启用配置的影响，所有减少量会累加。
小红最多可以选择 K 个节点启用优先转发。请计算整条通路能够达到的最小总时延。

输入输出

输入描述
第一行输入两个整数 N,K 。
第二行输入 N 个整数 delay_0,delay_1,...,delay_N-1 。
第三行输入 N 个整数 win_0,win_1,...,win_N-1 。
第四行输入 N 个整数 opt_0,opt_1,...,opt_N-1 。
保证 3 ≤ N ≤ 50 ， 0 ≤ K ≤ 10 ， 0 ≤ delay_i,opt_i ≤ 10^7 ， 0 ≤ win_i ≤ 3 。
输出描述
输出一个整数，表示配置后的最小总时延。

样例共 1 组

样例 1 · 在节点 3 启用优先转发后，该节点的时延从 40 降为 0 ，总时延为 60 。
输入
4 1
10 20 30 40
1 0 2 0
15 25 12 100
输出
60

算法解析依据充分

考点：动态规划

数据规模 N ≤ 50 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 50，K ≤ 10
  • 元素值域：delay_i ≤ 10000000，opt_i ≤ 10000000，win_i ≤ 3（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：动态规划

本题切入点

N≤50、可启用 K≤10 且影响窗口 win_i≤3：按位置做 DP，状态记「已启用数量」，转移时枚举当前位置是否启用并累加对后续窗口的时延削减（每点下限 0）。

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 N ≤ 50，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 元素值域最大到 10000000 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 4 1 / 10 20 30 40 / 1 0 2 0 / 15 25 12 100 → 输出 60

在节点 3 启用优先转发后，该节点的时延从 40 降为 0 ，总时延为 60 。

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

本题来源：2026年-华为-05月22号开发岗。

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