配点 : 400 点
問題文
长度为 NM 序列 有 A ,初始每个元素的值为 0 或 1 。 您可以根据需要对此数组执行任意数量的以下操作: 满足
- 1 \leq l \leq r \leq NM 的整数 反转 l, r , A_l, A_{l+1}, ... , A_r 的值。
操作后, A 必须满足以下条件: 每个都令人满意
- 1 \leq i \leq M 每一个都满足 i , A_i = A_{i+M} = A_{i+2M} = ... = A_{i+(N-1)M} 满意。
找出所需的最少操作数。
制約
- 1 \leq N,M \leq 2000
- A_i 是 给出了 0 或 1 (1 \leq i \leq NM)
- 所有输入均为整数 如果有办法做到
入力
输入是按以下格式从标准输入给出的。
N M
A_1 A_2 ... A_M
A_{M+1} A_{M+2} ... A_{2M}
\vdots
A_{(N-1)M+1} A_{(N-1)M+2} ... A_{NM}
出力
请将答案输出在一行内。
入力例 1
3 4 1 0 0 1 0 1 0 0 1 1 1 0
出力例 1
2
首先, 如果你操作为 l = 7, r = 7 ,它将如下所示:
1 0 0 1 0 1 1 0 1 1 1 0
并且, 当按 l = 2, r = 5 操作时,变为如下,满足条件。
1 1 1 0 1 1 1 0 1 1 1 0
在这种情况下,操作次数为 2 次, 由于小于 1 的操作无法满足条件, 2 。
入力例 2
7 5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
出力例 2
3
2,4,6 为了反转该行中的所有元素, 通过执行 3 次
- l = 7, r = 12
- l = 19, r = 24
- l = 31, r = 36
运算即可满足该条件,这是最小运算次数。
入力例 3
1 7 1 0 0 1 0 1 1
出力例 3
0
N = 1 始终满足条件,因此无需执行任何操作。此时 0 。