题解

思路

先独立计算每一行建一座桥的最小费用。设当前桥墩放在第 $j$ 列，前一个桥墩可以位于 $j-d-1$ 到 $j-1$ 的任意列。因此行内是一个带滑动窗口最小值的动态规划。

得到每一行的最小费用后，问题只剩下在这些行费用中选择长度为 $k$ 的连续子数组并最小化其和。

做法

对一行从左到右计算状态。第一列状态为其安装费用。计算第 $j$ 列时，取前面至多 $d+1$ 列状态的最小值，再加上当前格子的安装费用。用单调队列维护这个滑动窗口最小值，即可在线性时间内求出最后一列的状态。

对所有行得到费用数组后，用长度为 $k$ 的滑动窗口求最小连续和。

任意合法桥的最后一个桥墩都有一个满足距离限制的前驱，动态规划枚举了所有可能前驱；反之，每次转移连接的两根桥墩都满足距离限制，所以状态恰好表示合法方案的最小费用。行之间互不影响，最后只需按题意选连续 $k$ 行。

复杂度

每个格子只进出单调队列一次。每个测试用例的时间复杂度为 $O(nm)$，空间复杂度为 $O(m+n)$。