← 返回题目列表

Codeforces · 1941/E

E. 鲁道夫和 k 布里奇斯

中文机器翻译题面 查看原题

伯纳德喜欢拜访鲁道夫,但他总是迟到。问题是伯纳德必须乘坐渡轮过河。鲁道夫决定帮助他的朋友解决这个问题。

河流是由 $$$n$$$ 行和 $$$m$$$ 列组成的网格。第 $$$i$$$ 行和第 $$$j$$$ 列的交集包含数字 $$$a_{i,j}$$$ — 相应单元格中的深度。第一列和最后一列中的所有单元格都对应于河岸,因此它们的深度为 $$$0$$$。

河流可能看起来像这样。

Rudolf 可以选择行 $$$(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$$$。

只建造一座桥很无聊。因此,鲁道夫决定在河流的连续行上建造$$$k$$$桥梁,即选择一些$$$i$$$ ($$$1 \le i \le n - k + 1$$$)并在$$$i, i + 1, \ldots, i + k - 1$$$的每一行上独立建造一座桥梁。帮助鲁道夫最大限度地降低安装支撑的总成本。

输入

第一行包含一个整数 $$$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

输出 #1

4
8
4
15
14

注意

在第一个测试用例中,在第二行建造一座桥最有利可图。

这不是俯视图,而是侧视图:灰色单元格 - 桥本身,白色单元格是空的,黑色单元格 - 支撑,蓝色单元格 - 水,棕色单元格 - 河底。

在第二个测试用例中,在第二行和第三行上建造桥梁最有利可图。支撑物将放置在单元格 $$$(2, 3)$$$、$$$(3, 2)$$$ 以及河岸上。

在第三个测试用例中,可以沿着河岸放置支撑物。