← 返回题目列表

AtCoder · jag2017summer_day1_g

G. 旅游问题

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

問題文

旅游者先生 2 列表。

2 每个列表的长度是 N 列表的i 第 j 是 A_{i,j} 。 A_{i,j} 是正整数或负整数; 不是0 。

游客正在尝试对这些列表执行以下操作。

  • 首先,2 将两个列表中的所有负整数重写为正整数。此时,原来相同的数字必须重写为相同的数字,不同的数字必须重写为不同的数字。
  • 接下来,垂直 2 广场旁边 N 准备一张纸,上面写着方块,i 行目 j 在柱广场 写入第 i 第 j 个数字。
  • 最后,用剪刀剪掉相邻方格中写有不同数字的边缘和外框。然后纸张将被分成几块,因此数一下碎片的数量。

游客先生试图通过重写负整数来尽可能减少分隔的部分。 这张纸会被分成多少张?

制約

  • 1≦N≦10^5
  • 1≦|A_{i,j}|≦300

入力

输入是按以下格式从标准输入给出的。

N
A_{1,1} A_{1,2} ... A_{1,N}
A_{2,1} A_{2,2} ... A_{2,N}

出力

打印纸张分离时的张数。


入力例 1

5
1 2 1 2 1
-1 -2 -3 -3 -3

出力例 1

5

例如 -1 除以 999 当改写为-2 除以 2 当改写为-3 除以 1 时,就变成如下图所示,且个数最少。 5 件。

92e7ebbff942cc1af02ea1a3e5aa7a75.png

入力例 2

15
1 -1 1 -1 -1 -2 2 -1 3 3 3 -3 -2 -2 1
2 -1 1 1 -1 -2 -1 2 -2 3 3 -2 -2 -2 3

出力例 2

9