CF1941E · Rudolf and k Bridges

• 难度：1600
• 标签：binary search、data structures、dp、two pointers
• 链接：https://codeforces.com/problemset/problem/1941/E
• 时间限制：2 seconds　内存限制：256 megabytes
• 出现位置：Day25-二分-DP-数据结构综合

中文题意

河流是一个 $n$ 行 $m$ 列的网格。第 $i$ 行第 $j$ 列交点处的数 $a_{i,j}$ 表示该格的水深。第一列和最后一列的所有格子都是河岸，深度为 $0$。

Rudolf 可以选择某一行 $(i,1), (i,2), \ldots, (i,m)$，在其上建一座桥。他可以在该行的每个格子安装桥墩，在格子 $(i,j)$ 安装桥墩的花费为 $a_{i,j}+1$。桥墩的安装需满足以下条件：

• 格子 $(i,1)$ 必须安装桥墩；
• 格子 $(i,m)$ 必须安装桥墩；
• 任意两个相邻桥墩之间的距离不超过 $d$。桥墩 $(i, j_1)$ 与 $(i, j_2)$ 之间的距离定义为 $|j_1 - j_2| - 1$。

只建一座桥太无聊了。因此 Rudolf 决定在连续的若干行上建 $k$ 座桥：即选择某个 $i$（$1 \le i \le n-k+1$），在第 $i, i+1, \ldots, i+k-1$ 行上各自独立地建一座桥。请帮 Rudolf 使安装桥墩的总花费最小。

输入格式（中文）

第一行一个整数 $t$（$1 \le t \le 10^3$），表示测试数据组数。

每组数据第一行四个整数 $n$、$m$、$k$、$d$（$1 \le k \le n \le 100$，$3 \le m \le 2 \cdot 10^5$，$1 \le d \le m$），分别表示网格的行数、列数、桥的数量以及相邻桥墩间的最大距离。

接下来 $n$ 行，第 $i$ 行 $m$ 个正整数 $a_{i,j}$（$0 \le a_{i,j} \le 10^6$，$a_{i,1} = a_{i,m} = 0$），为各格的水深。

保证所有测试数据的 $n \cdot m$ 之和不超过 $2 \cdot 10^5$。

输出格式（中文）

对每组数据输出一个整数——安装桥墩的最小总花费。

样例

样例 1

输入：

5
3 11 1 4
0 1 2 3 4 5 4 3 2 1 0
0 1 2 3 2 1 2 3 3 2 0
0 1 2 3 5 5 5 5 5 2 0
4 4 2 1
0 3 3 0
0 2 1 0
0 1 2 0
0 3 3 0
4 5 2 5
0 1 1 1 0
0 2 2 2 0
0 2 1 1 0
0 3 2 1 0
1 8 1 1
0 10 4 8 4 4 2 0
4 5 3 2
0 8 4 4 0
0 3 4 8 0
0 8 1 10 0
0 10 1 5 0

输出：

4
8
4
15
14