A11270. Rudolf and k Bridges
编程题
普及/提高-
知识点
题目描述
The first line contains a single integer $t$ $(1 \le t \le 10^3)$ — the number of test cases. The descriptions of the test cases follow.
The first line of each test case contains four integers $n$ , $m$ , $k$ , and $d$ ( $1 \le k \le n \le 100$ , $3 \le m \le 2 \cdot 10^5$ , $1 \le d \le m$ ) — the number of rows and columns of the field, the number of bridges, and the maximum distance between supports.
Then follow $n$ lines, $i$ -th line contains $m$ positive integers $a_{i, j}$ ( $0 \le a_{i, j} \le 10^6$ , $a_{i, 1} = a_{i, m} = 0$ ) — the depths of the river cells.
It is guaranteed that the sum of $n \cdot m$ for all sets of input data does not exceed $2 \cdot 10^5$ .
The first line of each test case contains four integers $n$ , $m$ , $k$ , and $d$ ( $1 \le k \le n \le 100$ , $3 \le m \le 2 \cdot 10^5$ , $1 \le d \le m$ ) — the number of rows and columns of the field, the number of bridges, and the maximum distance between supports.
Then follow $n$ lines, $i$ -th line contains $m$ positive integers $a_{i, j}$ ( $0 \le a_{i, j} \le 10^6$ , $a_{i, 1} = a_{i, m} = 0$ ) — the depths of the river cells.
It is guaranteed that the sum of $n \cdot m$ for all sets of input data does not exceed $2 \cdot 10^5$ .
输入格式
For each test case, output a single number — the minimum total cost of supports installation.
输出格式
In the first test case, it is most profitable to build a bridge on the second row.
 It is not a top view, but side view: gray cells — bridge itself, white cells are empty, black cells — supports, blue cells — water, brown cells — river bottom.In the second test case, it is most profitable to build bridges on the second and third rows. The supports will be placed in cells $(2, 3)$ , $(3, 2)$ , and on the river banks.
In the third test case the supports can be placed along the river banks.
 It is not a top view, but side view: gray cells — bridge itself, white cells are empty, black cells — supports, blue cells — water, brown cells — river bottom.In the second test case, it is most profitable to build bridges on the second and third rows. The supports will be placed in cells $(2, 3)$ , $(3, 2)$ , and on the river banks.
In the third test case the supports can be placed along the river banks.
输入输出样例
输入 #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
说明/提示
In the first test case, it is most profitable to build a bridge on the second row.
 It is not a top view, but side view: gray cells — bridge itself, white cells are empty, black cells — supports, blue cells — water, brown cells — river bottom.In the second test case, it is most profitable to build bridges on the second and third rows. The supports will be placed in cells $(2, 3)$ , $(3, 2)$ , and on the river banks.
In the third test case the supports can be placed along the river banks.
 It is not a top view, but side view: gray cells — bridge itself, white cells are empty, black cells — supports, blue cells — water, brown cells — river bottom.In the second test case, it is most profitable to build bridges on the second and third rows. The supports will be placed in cells $(2, 3)$ , $(3, 2)$ , and on the river banks.
In the third test case the supports can be placed along the river banks.