RiseOJ – 소는 왜 길을 건넜을까 II

설명

농부 존은 $$N$$ 개 품종의 소를 키우며 ( $1 \leq N \leq 1000$ ), 품종들은 편의상 $1 \ldots N$ 번으로 번호가 매겨져 있다. 어떤 품종 쌍은 다른 쌍보다 사이가 좋은데, 이 성질은 품종 ID로 쉽게 특징지을 수 있다. 품종 $$a$$ 와 $$b$$ 는 $|a - b| \leq 4$ 이면 친하고, 그렇지 않으면 친하지 않다.

FJ의 농장을 가로질러 긴 도로가 지나간다. 도로의 한쪽에는 $$N$$ 개의 들판이 순서대로 놓여 있고(품종마다 하나씩 지정), 도로의 다른 쪽에도 $$N$$ 개의 들판이 순서대로 놓여 있다(역시 품종마다 하나씩). 소들이 도로를 안전하게 건널 수 있도록 FJ는 도로 위에 횡단보도를 그리려 한다. 각 횡단보도는 도로 한쪽의 들판과 다른 쪽의 들판을 연결해야 하는데, 두 들판의 품종 ID가 친해야 한다(소들이 다른 품종의 들판에 들어가도, 그 품종과 친하기만 하면 괜찮다). 각 들판에는 최대 하나의 횡단보도만 연결될 수 있다(즉, 횡단보도들은 끝점에서 만나지 않는다).

FJ의 농장을 지나는 도로 양쪽의 $$N$$ 개 들판의 순서가 주어질 때, 어느 두 개도 교차하지 않도록 도로 위에 그릴 수 있는 횡단보도의 최대 개수를 구하도록 FJ를 도와주자.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ 이 주어진다. 다음 $$N$$ 개의 줄은 도로 한쪽 들판들의 순서를 품종 ID로 나타낸다. 각 품종 ID는 $1 \ldots N$ 범위의 정수이다. 마지막 $$N$$ 개의 줄은 도로 다른 쪽 들판들의 순서를 품종 ID로 나타낸다. 각 품종 ID는 각 순서에 정확히 한 번씩 나타난다.

출력 형식

농부 존이 도로 위에 그릴 수 있는, 서로 겹치지 않는 "친한 횡단보도"의 최대 개수를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 nocross.in · 출력을 쓸 파일 nocross.out

예제 1

입력

출력

문제 정보

riseoj 작성

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

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

태그

JudgeUSACO

소는 왜 길을 건넜을까 II

평가 및 의견

풀이 제출