解题思路
由于 winsize[i]≤3,配置节点 i 的影响范围只会覆盖区间 [i,min(N−1,i+winsize[i])],也就是说一个节点 i 的延迟最多只会被它前面 3 个节点以及它自己影响。
因此可以使用状态压缩动态规划。
设 dp[c][mask] 表示当前处理到某个节点前,已经选择了 c 个优先转发节点,最近 3 个节点的选择状态为 mask 时的最小总延迟。
处理节点 i 时,有两种选择:
题目内容
有一个由 N 个数据交换节点(编号为 0 到 N−1)组成的新型数据传输网络。数据包从头节点 0 发送,按照编号顺序依次经过每个节点 i 的处理,最终到达尾节点 N−1。在每个节点 i 处理时,会产生 delay[i] 单位的处理时延。
每个数据交换节点 i 支持配置优先转发模式,它将会在数据包中添加特殊的标记,使数据包在本节点和后续 win_size[i] 个节点处理时走优先转发通道,降低处理时延(win_size[i] 不包含本节点,若 i+win_size[i]≥N,则只有 i∼N−1 节点受影响)。受该标记影响的节点 j 所产生的处理时延将不再是 delay[j],而是 delay[j]−opt_delay[i](opt_delay[i] 为时延优化值,若 opt_delay[i]>delay[j],则节点 j 产生的处理时延为 0)。如果某个节点被前面多个节点的优先转发模式影响,它的处理时延会被减少多次。
你的目标是在整个网络中最多选择 K 个节点配置优先转发模式,使数据包达尾节点 N 时,产生的总处理时延最小,输出最小的总处理时延。
解答要求
时间限制:C/C++ 1000ms,其他语言:2000ms
内存限制:C/C++ 256MB,其他语言:512MB
输入
第一行:两个整数 N,K,其中 N 是整个网络的数据交换节点数,K 是最多可以配置优先转发模式的数据交换节点数。
第二行:N 个整数,表示每个节点默认情况下产生的处理时延 delay[0..N−1]。
第三行:N 个整数,表示如果在第 i 个节点配置优先转发模式,其影响的后续节点数 win_size[0..N−1]。
第四行:N 个整数,表示如果在第 i 个节点配置优先转发模式,其时延优化值 opt_delay[0..N−1]。
- 3≤N≤50
- 0≤K≤10
- 0≤delay[i]≤107
- 0≤win_size[0..N−1]≤3
- 0≤opt_delay[i]≤107
- 所有输入数据均为整数。
输出
一个整数,表示通过配置后所能得到的最小的总处理时延。
样例1
输入:
3 1
50 40 30
3 0 1
0 50 10
输出:
80
解释:
- 若在节点 0 配置,由于其时延优化值为 0,无任何收益,总处理时延为 50+40+30=120。
- 若在节点 1 配置,其作用范围为自身节点,节点 1 的处理时延从 40 变为 0(40−50<0),总处理时延为 50+0+30=80,此选择最优。
- 若在节点 2 配置,虽然其作用范围为 1,但由于无后续节点,因此只有自身节点有收益,处理时延从 30 变为 20(30−10=20),总处理时延为 50+40+20=110。
样例2
输入:
5 2
10 20 30 40 50
1 0 1 3 2
15 20 0 30 35
输出:
65
解释:
- 若在节点 0 和节点 1 配置优先转发模式,节点 0 处理时延从 10 变为 0(10−15<0),节点 1 会被优先转发模式影响 2 次,处理时延从 20 变为 0(20−15−20<0)。总处理时延为 0+0+30+40+50=120。
- 若在节点 0 和节点 2 配置优先转发模式,节点 0 处理时延从 10 变为 0(10−15<0),节点 1 处理时延从 20 变为 5(20−15=5),其余节点无变化。总处理时延为 0+5+30+40+50=125。
- 若在节点 0 和节点 3 配置优先转发模式,节点 0 处理时延从 10 变为 0(10−15<0),节点 1 处理时延从 20 变为 5(20−15=5),节点 3 处理时延从 40 变为 10(40−30=10),节点 4 处理时延从 50 变为 20(50−30=20)。总处理时延为 0+5+30+10+20=65,此组合最优。
- 其余组合类似:
- 若在节点 0 和节点 4 配置优先转发模式,总处理时延为 0+5+30+40+15=90。
- 若在节点 1 和节点 2 配置优先转发模式,总处理时延为 10+0+30+40+50=130。
- 若在节点 1 和节点 3 配置优先转发模式,总处理时延为 10+0+30+10+20=70。
- 若在节点 1 和节点 4 配置优先转发模式,总处理时延为 10+0+30+40+15=95。
- 若在节点 2 和节点 3 配置优先转发模式,总处理时延为 10+20+30+10+20=90。
- 若在节点 2 和节点 4 配置优先转发模式,总处理时延为 10+20+30+40+15=115。
- 若在节点 3 和节点 4 配置优先转发模式,总处理时延为 10+20+30+10+0=70。