← 返回题目列表

AtCoder · pakencamp_2025_day1_k

K. 好网格

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

配点 : 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 。