原题链接:Codeforces1216F
题意
有 $n$ 个房间从左至右编号为 $1\text{~}n$,房间 $i$ 直接连入网络的代价是 $i$,给定一个长度为 $n$ 的 $01$ 串,$1$ 表示该房间可以放置路由器,在房间 $i$ 放置路由器的代价同样为 $i$,给定路由器能够覆盖的半径为 $k$,即在 $i$ 放置路由器后,$[i-k,i+k]$ 均能连上 Wi-Fi 。求让所有房间连上 Wi-Fi 的最小代价。
解法
单调队列优化 DP
考虑房间 $i$ 最多有 $3$ 种状态:
- 不直接连 Wi-Fi 也不放置路由器。
- 直接连 Wi-Fi 。
- 放置路由器。
定义状态 $f[i][j]$ 表示将 $1\text{~}i$ 全部连网且第 $i$ 个房间的状态为 $j$ 的最小代价。
- $f[i][0]$ 表示 $1\text{~}i$ 全部连上网,且第 $i$ 个房间不直接连网且不放置路由器的最小代价。
- $f[i][1]$ 表示 $1\text{~}i$ 全部连上网,且第 $i$ 个房间直接连网的最小代价。
- $f[i][2]$ 表示 $1\text{~}i$ 全部连上网,且第 $i$ 个房间放置路由器的最小代价。
状态转移(自己乱搞了一波转移 qwq )
$$ f[i][1] = \min\lbrace f[i - 1][0], f[i - 1][1], f[i - 1][2]\rbrace + i $$
$$ f[i][2] = \min\lbrace f[\max(0, i - k - 1)][0], f[\max(0, i - k - 1)][1], f[\max(0, i - k - 1)][2]\rbrace+ i $$
$$ f[i][2] = \min(f[i][1], f[i][2]) $$
$$ f[i][0] = f[q[hh]][2] $$
$f[i][0]$ 比较特殊,因为他需要由其他的路由器覆盖到,而在 $i$ 左侧且能够覆盖到 $i$ 的路由器位置范围为 $[i-k,i-1]$,这里如果直接暴力枚举该区间内某一个点放置路由器来转移,显然不可取,可以发现这里要求的是一个长度为 $k$ 的滑动窗口中 $f[j][2]$ 的最值,可以用单调队列来优化。即用单调队列维护 $j\in [i-k,i-1]$ 下标区间中 $f[j][2]$ 的最小值的下标(队头元素 q[hh]
)。
$$ \text{Ans}=\min\lbrace f[n][0],f[n][1],f[n][2]\rbrace $$
代码
|
|