AT_abc264_f [ABC264F] Monochromatic Path

题目描述

有一个 $H$ 行 $W$ 列的网格，每个格子被涂成白色或黑色。对于满足 $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$ 时，格子 $(i, j)$ 是黑色。

你可以任意次（也可以一次都不做）重复以下两种操作中的任意一种：

• 选择一个满足 $1 \leq i \leq H$ 的整数，支付 $R_i$ 日元后，将网格从上到下第 $i$ 行的所有格子的颜色反转（白色变黑色，黑色变白色）。
• 选择一个满足 $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}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

9

输入输出样例 #2

输入 #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

说明/提示

约束

• $2 \leq H, W \leq 2000$
• $1 \leq R_i \leq 10^9$
• $1 \leq C_j \leq 10^9$
• $A_{i, j} \in \{0, 1\}$
• 输入均为整数

样例解释 1

用 0 表示白色格子，1 表示黑色格子。对于初始状态的网格，支付 $R_2 = 3$ 日元将第 $2$ 行的所有格子反转后，网格变为：

0100
0100
1010

接着，支付 $C_2 = 6$ 日元将第 $2$ 列的所有格子反转后，网格变为：

0000
0000
1110

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

由 ChatGPT 4.1 翻译