CF1941E Rudolf and k Bridges

Bernard 喜欢拜访 Rudolf，但他总是迟到。问题在于 Bernard 需要乘渡船过河。Rudolf 决定帮助他的朋友解决这个问题。 这条河可以表示为一个 $n$ 行 $m$ 列的网格。在第 $i$ 行第 $j$ 列的交点处有一个数 $a_{i,j}$，表示该格子的水深。所有第一列和最后一列的格子都对应河岸，因此它们的深度为 $0$。  这条河可能长这样。Rudolf 可以选择第 $i$ 行的 $(i,1), (i,2), \ldots, (i,m)$，并在这一行上建一座桥。在该行的每个格子中，他可以安装一个桥墩。在格子 $(i,j)$ 安装桥墩的费用为 $a_{i,j}+1$。安装桥墩时必须满足以下条件： 1. 必须在格子 $(i,1)$ 安装桥墩； 2. 必须在格子 $(i,m)$ 安装桥墩； 3. 任意一对相邻桥墩之间的距离不能超过 $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$。

对于每个测试用例，输出一个整数，表示安装所有桥墩的最小总费用。

在第一个测试用例中，最优方案是在第二行建桥。  这不是俯视图，而是侧视图：灰色格子表示桥本身，白色格子为空，黑色格子为桥墩，蓝色格子为水，棕色格子为河底。在第二个测试用例中，最优方案是在第二行和第三行建桥。桥墩将分别放在 $(2,3)$、$(3,2)$ 以及河岸上。 在第三个测试用例中，桥墩可以全部放在河岸上。 由 ChatGPT 4.1 翻译