#PU718. USACO 2017 February Contest, Gold — Problem 2. Why Did the Cow Cross the Road II

    ID: 1369 传统题 文件IO:nocross 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb17来源:usaco.orgscoring:equal_test_cases

USACO 2017 February Contest, Gold — Problem 2. Why Did the Cow Cross the Road II

USACO 2017 February Contest, Gold — Problem 2. Why Did the Cow Cross the Road II

题目描述

Farmer John raises NN breeds of cows (1≤N≤10001 \leq N \leq 1000), conveniently numbered 1…N1 \ldots N. Some pairs of breeds are friendlier than others, a property that turns out to be easily characterized in terms of breed ID: breeds aa and bb are friendly if ∣a−b∣≤4|a - b| \leq 4, and unfriendly otherwise. A long road runs through FJ's farm. There is a sequence of NN fields on one side of the road (one designated for each breed), and a sequence of NN fields on the other side of the road (also one for each breed). To help his cows cross the road safely, FJ wants to draw crosswalks over the road. Each crosswalk should connect a field on one side of the road to a field on the other side where the two fields have friendly breed IDs (it is fine for the cows to wander into fields for other breeds, as long as they are friendly). Each field can be accessible via at most one crosswalk (so crosswalks don't meet at their endpoints). Given the ordering of NN fields on both sides of the road through FJ's farm, please help FJ determine the maximum number of crosswalks he can draw over his road, such that no two intersect.

输入格式

The first line of input contains NN. The next NN lines describe the order, by breed ID, of fields on one side of the road; each breed ID is an integer in the range 1…N1 \ldots N. The last NN lines describe the order, by breed ID, of the fields on the other side of the road. Each breed ID appears exactly once in each ordering.

输出格式

Please output the maximum number of disjoint "friendly crosswalks" Farmer John can draw across the road.

数据范围

(见题面原文)

样例

样例 1

6
1
2
3
4
5
6
6
5
4
3
2
1
5
Problem credits: Brian Dean