A7012. 鲁道夫与 k 座桥
编程题
普及+/提高
知识点
题目描述
伯纳德想去拜访鲁道夫，但他总是迟到，因为他必须乘渡轮过河。为了帮助朋友，鲁道夫决定在河上建桥。
这条河可以看作一个 $n$ 行 $m$ 列的网格。第 $i$ 行第 $j$ 列的单元格包含一个数字 $a_{i,j}$，表示该处的河水深度。第一列和最后一列代表河岸，因此它们的深度始终为 $0$。
鲁道夫可以选择某一行 $i$，并在该行建造一座桥。建桥需要在该行的若干个单元格中安装桥墩。在单元格 $(i, j)$ 安装桥墩的代价为 $a_{i,j} + 1$。
安装桥墩必须满足以下条件：
1. 必须在第 $1$ 列的单元格 $(i, 1)$ 安装桥墩；
2. 必须在第 $m$ 列的单元格 $(i, m)$ 安装桥墩；
3. 任意两个相邻桥墩之间的距离不能超过 $d$。具体来说，如果两个相邻桥墩分别位于 $(i, j_1)$ 和 $(i, j_2)$（假设 $j_1 < j_2$），则它们之间的距离定义为 $|j_1 - j_2| - 1$。条件要求 $|j_1 - j_2| - 1 \le d$（即 $j_2 - j_1 \le d + 1$）。
只建一座桥太无聊了。因此，鲁道夫决定在**连续的** $k$ 行上分别建造一座桥。也就是说，他需要选择一个起始行 $i$ ($1 \le i \le n - k + 1$)，并在第 $i, i+1, \dots, i+k-1$ 行上各建一座桥。
请你帮助鲁道夫计算，在满足上述条件的前提下，建造这 $k$ 座桥所需的桥墩安装总代价的最小值是多少。
这条河可以看作一个 $n$ 行 $m$ 列的网格。第 $i$ 行第 $j$ 列的单元格包含一个数字 $a_{i,j}$，表示该处的河水深度。第一列和最后一列代表河岸，因此它们的深度始终为 $0$。
鲁道夫可以选择某一行 $i$，并在该行建造一座桥。建桥需要在该行的若干个单元格中安装桥墩。在单元格 $(i, j)$ 安装桥墩的代价为 $a_{i,j} + 1$。
安装桥墩必须满足以下条件：
1. 必须在第 $1$ 列的单元格 $(i, 1)$ 安装桥墩；
2. 必须在第 $m$ 列的单元格 $(i, m)$ 安装桥墩；
3. 任意两个相邻桥墩之间的距离不能超过 $d$。具体来说，如果两个相邻桥墩分别位于 $(i, j_1)$ 和 $(i, j_2)$（假设 $j_1 < j_2$），则它们之间的距离定义为 $|j_1 - j_2| - 1$。条件要求 $|j_1 - j_2| - 1 \le d$（即 $j_2 - j_1 \le d + 1$）。
只建一座桥太无聊了。因此，鲁道夫决定在**连续的** $k$ 行上分别建造一座桥。也就是说，他需要选择一个起始行 $i$ ($1 \le i \le n - k + 1$)，并在第 $i, i+1, \dots, i+k-1$ 行上各建一座桥。
请你帮助鲁道夫计算，在满足上述条件的前提下，建造这 $k$ 座桥所需的桥墩安装总代价的最小值是多少。
输入格式
第一行包含一个整数 $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$ 行，每行包含 $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$。
对于每组测试数据：
第一行包含四个整数 $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$ 行，每行包含 $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
输出 #1
4 8 4 15 14
说明/提示
在第一个测试用例中，最优方案是在第二行建桥。
这不是俯视图，而是侧视图：灰色格子表示桥本身，白色格子为空，黑色格子为桥墩，蓝色格子为水，棕色格子为河底。在第二个测试用例中，最优方案是在第二行和第三行建桥。桥墩将分别放在 $(2,3)$、$(3,2)$ 以及河岸上。
在第三个测试用例中，桥墩可以全部放在河岸上。
这不是俯视图，而是侧视图：灰色格子表示桥本身，白色格子为空，黑色格子为桥墩，蓝色格子为水，棕色格子为河底。在第二个测试用例中，最优方案是在第二行和第三行建桥。桥墩将分别放在 $(2,3)$、$(3,2)$ 以及河岸上。
在第三个测试用例中，桥墩可以全部放在河岸上。