Monochromatic Path

题目描述

我们有一个 $H$ 行 $W$ 列的网格。每个方格被涂成白色或黑色。 对于每个整数对 $(i, j)$ 满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$，从上往下第 $i$ 行、从左往右第 $j$ 列的方格（我们简记为方格 $(i, j)$）的颜色由 $A_{i, j}$ 表示。 当 $A_{i, j} = 0$ 时方格 $(i, j)$ 为白色，当 $A_{i, j} = 1$ 时为黑色。 你可以任意次数（可能为 $0$ 次）以任意顺序执行下述操作：

选择一个整数 $i$，使得 $1 \leq i \leq H$，付出 ¥$R_i$，并将网格中第 $i$ 行的每个方格的颜色取反。（白色方格涂成黑色，黑色方格涂成白色。） 选择一个整数 $j$，使得 $1 \leq j \leq W$，付出 ¥$C_j$，并将网格中第 $j$ 列的每个方格的颜色取反。

输出使下述条件成立的最小总费用：

存在一条从方格 $(1, 1)$ 到方格 $(H, W)$ 的路径，该路径可由反复向下或向右移动得到，使得路径上的所有方格（包括方格 $(1, 1)$ 和方格 $(H, W)$）颜色相同。

在本题的约束下我们可以证明总能在有限次数的操作后使条件成立。

输入格式

输入从标准输入按如下格式给出： $H$ $W$ $R_1$ $R_2$ $\ldots$ $R_H$ $C_1$ $C_2$ $\ldots$ $C_W$ $A_{1, 1}A_{1, 2}\ldots A_{1, W}$ $A_{2, 1}A_{2, 2}\ldots A_{2, W}$ $\vdots$ $A_{H, 1}A_{H, 2}\ldots A_{H, W}$

输出格式

输出答案。

3 4
4 3 5
2 6 7 4
0100
1011
1010

9

0100
0100
1010

0000
0000
1110

15 20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78
39 97 12 53 62 32 38 84 49 93 53 26 13 25 2 76 32 42 34 18
01011100110000001111
10101111100010011000
11011000011010001010
00010100011111010100
11111001101010001011
01111001100101011100
10010000001110101110
01001011100100101000
11001000100101011000
01110000111011100101
00111110111110011111
10101111111011101101
11000011000111111001
00011101011110001101
01010000000001000000

125

提示

$2 \leq H, W \leq 2000$ $1 \leq R_i \leq 10^9$ $1 \leq C_j \leq 10^9$ $A_{i, j} \in \lbrace 0, 1\rbrace$ 输入中的所有值均为整数。我们用 $0$ 表示白色方格，用 $1$ 表示黑色方格。 在初始网格上，你可以付出 $R_2 = 3$ 日元将从上往下第 $2$ 行的每个方格的颜色取反，使得网格变为：

然后，你可以付出 $C_2 = 6$ 日元将从左往右第 $2$ 列的每个方格的颜色取反，使得网格变为：

现在存在一条从方格 $(1, 1)$ 到方格 $(3, 4)$ 的路径，其上所有方格颜色相同（例如路径 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$）。 总费用为 $3+6 = 9$ 日元，这是最小可能的。

标签: AtCoder|abc264F

来源

AtCoder|abc264F