Why Did the Cow Cross the Road II

题目描述

农夫 John 继续思考前一题中关于奶牛穿过他农场道路的问题。他意识到，若某些品种之间彼此友好，那么它们之间的相互影响实际上是可以接受的，而“友好”这一性质可以很容易地用品种编号来刻画：当且仅当 $|a - b| \leq 4$ 时，品种 $a$ 与 $b$ 友好，否则不友好。 只要品种之间友好，奶牛进入为其他品种指定的田地也是可以的。 给定道路两侧各 $N$ 块田地的排列顺序（同样地，道路两侧每个品种都恰好各有一块田地），请帮助农夫 John 确定他最多能在道路上画出多少条人行横道，使得任意两条横道不相交，并且每条横道连接的一对田地所包含的两个品种是友好的。每块田地最多只能通过一条横道到达（因此横道的端点也不能相同）。

输入格式

第一行输入为 $N$（$1 \leq N \leq 100,000$）。接下来 $N$ 行按品种编号描述道路一侧田地的顺序；每个品种编号是范围 $1 \ldots N$ 内的整数。最后 $N$ 行按品种编号描述道路另一侧田地的顺序。每个品种编号在每个顺序中都恰好出现一次。

输出格式

请输出农夫 John 最多能画出的互不相交的“友好横道”的数量。

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

5

提示

题目来源信息：Brian Dean

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum