Farmer John raises \(N\) breeds of cows (\(1 \leq N \leq 1000\)), conveniently
numbered \(1 \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
\(a\) and \(b\) are friendly if \(|a - b| \leq 4\), and unfriendly otherwise.

A long road runs through FJ's farm. There is a sequence of \(N\) fields on
one side of the road (one designated for each breed), and a sequence of \(N\) 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 \(N\) 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.

Problem credits: Brian Dean

Problem credits: Brian Dean

The first line of input contains \(N\). The next \(N\)
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 \ldots N\). The last \(N\) 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.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Gold