← 返回题目列表

Codeforces · 2049/D

D. 切换键加退出键

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

在玩弄某种装置并被抓住后,龙 Evirir 决定充分利用他们的魔法技能 - 扭曲现实以快速逃脱!

给定一个网格,其中包含非负整数 $$$n$$$ 行和 $$$m$$$ 列以及整数 $$$k$$$。令 $$$(i, j)$$$ 表示从顶部算起第 $$$i$$$ 行和从左边算起第 $$$j$$$ 列中的单元格 ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$)。对于每个单元格 $$$(i, j)$$$,整数 $$$a_{i, j}$$$ 写入单元格 $$$(i, j)$$$ 上。

您最初位于 $$$(1, 1)$$$,并且想要前往 $$$(n, m)$$$。您只能向下或向右移动。也就是说,如果您位于$$$(i, j)$$$,则只能移动到$$$(i+1, j)$$$ 或$$$(i, j+1)$$$(如果对应的单元格存在)。

在开始移动之前,您可以多次执行以下操作:

- 选择 $$$1$$$ 和 $$$n$$$ 之间的整数 $$$i$$$ 并将行 $$$i$$$ 循环向左移动 $$$1$$$。形式上,对于所有整数 $$$j$$$ ($$$1 \le j \le m$$$),同时将 $$$a_{i,j}$$$ 设置为 $$$a_{i,(j \bmod m) + 1}$$$。

从 $$$(1, 1)$$$ 移动到 $$$(n, m)$$$ 后,令 $$$x$$$ 为移动前执行的操作数,令 $$$y$$$ 为写入到访问过的单元格上的整数之和(包括 $$$(1, 1)$$$ 和 $$$(n, m)$$$)。那么成本定义为$$$kx + y$$$。

求从 $$$(1, 1)$$$ 移动到 $$$(n, m)$$$ 的最低成本。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

第一行包含三个空格分隔的整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n、m \leq 200$$$、$$$0 \leq k \leq 10^9$$$)。

然后是 $$$n$$$ 行。第 $$$i$$$ 行包含 $$$m$$$ 以空格分隔的整数,$$$a_{i,1},\,a_{i,2},\,\ldots,\,a_{i,m}$$$ ($$$0 \leq a_{i,j} \leq 10^9$$$)。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$5 \cdot 10^4$$$。

输出

对于每个测试用例,输出一个整数,即从 $$$(1, 1)$$$ 移动到 $$$(n, m)$$$ 的最小成本。

示例

输入 #1

5
3 3 100
3 4 9
5 2 4
0 101 101
3 4 1
10 0 0 10
0 0 10 0
10 10 0 10
1 1 3
4
3 2 3
1 2
3 6
5 4
10 10 14
58 49 25 12 89 69 8 49 71 23
45 27 65 59 36 100 73 23 5 84
82 91 54 92 53 15 43 46 11 65
61 69 71 87 67 72 51 42 55 80
1 64 8 54 61 70 47 100 84 50
86 93 43 51 47 35 56 20 33 61
100 59 5 68 15 55 69 8 8 60
33 61 20 79 69 51 23 24 56 28
67 76 3 69 58 79 75 10 65 63
6 64 73 79 17 62 55 53 61 58

输出 #1

113
6
4
13
618

注意

在第一个测试用例中,最低成本 $$$113$$$ 可以实现如下:

1. 将第 3 行循环移位一次。网格现在变成 $$$$$$\begin{bmatrix}3 & 4 & 9\\5 & 2 & 4\\101 & 101 & 0\end{bmatrix}.$$$$$$
2. 移动如下:$$$(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$$$。

$$$x = 1$$$ 操作在移动之前完成。访问过的单元格上的整数之和为 $$$y = 3 + 4 + 2 + 4 + 0 = 13$$$。因此,成本为 $$$kx + y = 100 \cdot 1 + 13 = 113$$$。

在第二个测试用例中,可以将第 1 行移动一次,将第 2 行移动两次,将第 3 行移动三次。那么,网格就变成了 $$$$$$\begin{bmatrix}0 & 0 & 10 & 10\\10 & 0 & 0 & 0\\10 & 10 & 10 & 0\end{bmatrix}.$$$$$$

$$$x = 6$$$操作在移动之前完成,并且存在成本$$$y = 0$$$的路径。因此,成本为 $$$6 \cdot 1 + 0 = 6$$$。