Why Did the Cow Cross the Road II

题目描述

农夫 John 饲养了 $N$ 个品种的奶牛（$1 \leq N \leq 1000$），方便起见编号为 $1 \ldots N$。某些品种对比其他品种更友好，这一性质可以很容易地用品种编号来刻画：若品种 $a$ 与 $b$ 满足 $|a - b| \leq 4$，则它们是友好的，否则是不友好的。

一条长路穿过 FJ 的农场。道路的一侧有一列 $N$ 块田地（每个品种各对应一块），道路的另一侧也有一列 $N$ 块田地（同样每个品种各对应一块）。为了帮助奶牛安全过路，FJ 想在路上画一些人行横道。每条横道应连接道路一侧的一块田地与另一侧的一块田地，并且这两块田地对应的品种编号必须是友好的（奶牛走入其他品种的田地也没关系，只要它们是友好的）。

每块田地最多只能通过一条横道到达（因此横道在端点处不会相交）。给定道路两侧 $N$ 块田地的排列顺序，请帮助 FJ 确定他最多能画多少条横道，使得任意两条横道都不相交。

输入格式

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

输出格式

请输出农夫 John 最多可以在道路上画出的、互不相交的“友好横道”的数量。

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

5

提示

题目来源：Brian Dean

标签: USACO|2017|Gold

来源

USACO|2017|Gold