配点 : 100 点
通知
已发现该问题的假设解决方案是不正确的,并且可能无法在合理的时间内解决。非常抱歉。此问题也将从环球杯中删除。
我觉得这个问题可以在“外星人必须与至少另外两个外星人牵手”的条件下提出。
問題文
x 坐标和 y 坐标是 小于 0 以上 N 的整数的网格点 有一个外星人站在 (x, y) (别处)。
合計 N^2 每个人类外星人都有四只手。只是距离 1 似乎是 2 人类外星人可以互相牵手(创建双向连接)。
一开始,一些外星人对已经牵着手,他们的状态如下。
-
A_{i,j} = 1 时,(i, j) 中的外星人 (i, j+1) 中的外星人已经手牵着手(0 \le i < N,\ 0 \le j < N-1)。
-
B_{i,j} = 1 时,(i, j) 中的外星人 (i+1, j) 中的外星人已经手牵着手(0 \le i < N-1,\ 0 \le j < N)。
您可以执行以下操作 可以重复超过 0 次。 选择一个
- 只是距离 1 是 2 选择一个外星人并 2 与人牵手。
通过适当地执行这些操作,又一个 3 与人类外星人牵手的外星人数量 最大化。
制約
- 2 \le N \le 500
- A_{i,j} \in \lbrace 0,1\rbrace (0 \le i < N,\ 0 \le j < N-1)
- B_{i,j} \in \lbrace 0,1\rbrace (0 \le i < N-1,\ 0 \le j < N)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N
A_{0,0} A_{0,1} \dots A_{0,N-2}
\vdots
A_{N-1,0} A_{N-1,1} \dots A_{N-1,N-2}
B_{0,0} B_{0,1} \dots B_{0,N-1}
\vdots
B_{N-2,0} B_{N-2,1} \dots B_{N-2,N-1}
出力
又一个 3 打印与人类外星人牵手的外星人的最大数量。
入力例 1
4 000 010 010 000 0000 0110 0000
出力例 1
8

样本的初始状态如图1左侧所示。如图所示,另外 12 通过连接双手,总计 8 每个外星人都是 3 你可以与人牵手。这是可实现的最大值并且是最佳的。
入力例 2
7 001110 111011 100110 101111 100001 001001 010110 0101011 1001110 1101000 0001111 0111000 0110111
出力例 2
42