102645: [AtCoder]ABC264 F - Monochromatic Path
Description
Score : $500$ points
Problem Statement
We have a grid with $H$ rows and $W$ columns. Each square is painted either white or black. For each integer pair $(i, j)$ such that $1 \leq i \leq H$ and $1 \leq j \leq W$, the color of the square at the $i$-th row from the top and $j$-th column from the left (we simply denote this square by Square $(i, j)$) is represented by $A_{i, j}$. Square $(i, j)$ is white if $A_{i, j} = 0$, and black if $A_{i, j} = 1$.
You may perform the following operations any number of (possibly $0$) times in any order:
- Choose an integer $i$ such that $1 \leq i \leq H$, pay $R_i$ yen (the currency in Japan), and invert the color of each square in the $i$-th row from the top in the grid. (White squares are painted black, and black squares are painted white.)
- Choose an integer $j$ such that $1 \leq j \leq W$, pay $C_j$ yen, and invert the color of each square in the $j$-th column from the left in the grid.
Print the minimum total cost to satisfy the following condition:
- There exists a path from Square $(1, 1)$ to Square $(H, W)$ that can be obtained by repeatedly moving down or to the right, such that all squares in the path (including Square $(1, 1)$ and Square $(H, W)$) have the same color.
We can prove that it is always possible to satisfy the condition in a finite number of operations under the Constraints of this problem.
Constraints
- $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$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$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}$
Output
Print the answer.
Sample Input 1
3 4 4 3 5 2 6 7 4 0100 1011 1010
Sample Output 1
9
We denote a white square by 0 and a black square by 1.
On the initial grid, you can pay $R_2 = 3$ yen to invert the color of each square in the $2$-nd row from the top to make the grid:
0100 0100 1010
Then, you can pay $C_2 = 6$ yen to invert the color of each square in the $2$-nd row from the left to make the grid:
0000 0000 1110
Now, there exists a path from Square $(1, 1)$ to Square $(3, 4)$ such that all squares in the path have the same color (such as the path $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$). The total cost paid is $3+6 = 9$ yen, which is the minimum possible.
Sample Input 2
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
Sample Output 2
125
Input
题意翻译
在 $n\times m$ （$1 \leq n,m \leq 2000$）的网格图中，每个格子有 $0,1$ 两种，有两种操作： - 将第 $i$ 行元素反转，花费 $r_i$ 代价 - 将第 $j$ 列元素反转，花费 $c_j$ 代价 进行若干次上述操作后，使得图中存在一条从 $(1, 1)$ 到 $(n, m)$ 的路径，路径上的颜色相同 求为此的最小代价Output
问题描述
我们有一个有$H$行和$W$列的网格。每个方块都被涂成白色或黑色。对于每对整数$(i, j)$，如果$1 \leq i \leq H$和$1 \leq j \leq W$，则位于从顶部数第$i$行，从左数第$j$列的方块（我们简单地将这个方块表示为Square $(i, j)$）的颜色由$A_{i, j}$表示。如果$A_{i, j} = 0$，则Square $(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$列中每个方块的颜色。
打印满足以下条件的最小总成本：
- 存在一条从Square $(1, 1)$到Square $(H, W)$的路径，可以通过反复向右或向下移动来获得，使得路径中的所有方块（包括Square $(1, 1)$和Square $(H, W)$）具有相同的颜色。
我们可以证明，在本问题的约束下，总是在有限数量的操作中可以满足条件。
约束
- $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$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
$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}$
输出
打印答案。
样例输入 1
3 4 4 3 5 2 6 7 4 0100 1011 1010
样例输出 1
9
我们将白色方块表示为0，将黑色方块表示为1。
在初始网格上，您可以支付$R_2 = 3$日元来翻转网格中从顶部数第$2$行中每个方块的颜色，使网格变成：
0100 0100 1010
然后，您可以支付$C_2 = 6$日元来翻转网格中从左数第$2$列中每个方块的颜色，使网格变成：
0000 0000 1110
现在，存在一条从Square $(1, 1)$到Square $(3, 4)$的路径，使得路径中的所有方块都具有相同的颜色（例如，路径$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$）。支付的总成本为$3+6 = 9$日元，这是可能的最小值。
样例输入 2
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
样例输出 2
125