#P6119. [USACO17FEB] Why Did the Cow Cross the Road II G

[USACO17FEB] Why Did the Cow Cross the Road II G

题目背景

本题与 白金组同名题目 在题意上一致,唯一的差别是数据范围。

题目描述

Farmer John 饲养了 NN 种奶牛,编号从 11NN。一些品种的奶牛和其他奶牛间相处良好,事实证明,如果两个品种的奶牛编号分别为 a,ba,b,当 ab4|a-b| \leq 4 时,这两个品种的奶牛能友好相处,否则不能友好相处。

一条长长的道路贯穿整个农场,道路的左侧有 NN 个牧场(每个品种的奶牛恰好占据一个牧场),道路的右侧也有 NN 个牧场(每个品种的奶牛恰好占据一个牧场)。为了让奶牛们安全穿过马路,Farmer John 希望能在马路上画出一些人行道(牛行道?),要求这些人行道满足如下条件:

  1. 人行道从左侧的某个牧场出发,连接到右侧的某个牧场;
  2. 人行道连接的两个牧场的奶牛要能友好相处;
  3. 人行道不能在道路中间相交;
  4. 每个牧场只能与一条人行道相连。

你需要帮 FJ 求出最多能有多少条人行道。

输入格式

输入第一行一个整数 NN1N10001 \leq N \leq 1000)。

接下来 NN 行,每行一个整数 aia_i,代表道路左侧第 ii 个牧场的奶牛品种编号。

接下来 NN 行,每行一个整数 bib_i,代表道路右侧第 ii 个牧场的奶牛品种编号。

输出格式

输出最多能画多少条人行道。

6
1
2
3
4
5
6
6
5
4
3
2
1
5