레이팅 미적용농부 존은 앞선 문제에서 소개된, 소들이 농장을 지나는 도로를 건너는 문제를 계속 고민하고 있다. 그는 어떤 품종 쌍들 사이의 접촉은 두 품종이 친하다면 사실 괜찮다는 것을 깨닫는데, 이 성질은 품종 ID로 쉽게 특징지을 수 있다. 품종 \(a\)와 \(b\)는 \(|a - b| \leq 4\)이면 친하고, 그렇지 않으면 친하지 않다. 소들이 다른 품종으로 지정된 들판에 들어가도, 그 품종과 친하기만 하면 괜찮다.
FJ의 농장을 지나는 도로 양쪽의 \(N\)개 들판의 순서가 주어질 때(역시 양쪽 모두 품종마다 정확히 하나의 들판이 있다), 어느 두 개도 교차하지 않고 각 횡단보도가 친한 두 품종의 들판 쌍을 연결하도록 도로 위에 그릴 수 있는 횡단보도의 최대 개수를 구하도록 FJ를 도와주자. 각 들판에는 최대 하나의 횡단보도만 연결될 수 있다(즉, 횡단보도들은 끝점에서 만나지 않는다).
문제 출처: Brian Dean
문제 출처: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다 (\(1 \leq N \leq 100,000\)). 다음 \(N\)개의 줄은 도로 한쪽 들판들의 순서를 품종 ID로 나타낸다. 각 품종 ID는 \(1 \ldots N\) 범위의 정수이다. 마지막 \(N\)개의 줄은 도로 다른 쪽 들판들의 순서를 품종 ID로 나타낸다. 각 품종 ID는 각 순서에 정확히 한 번씩 나타난다.
농부 존이 도로 위에 그릴 수 있는, 서로 겹치지 않는 "친한 횡단보도"의 최대 개수를 출력한다.
nocross.in · 출력을 쓸 파일 nocross.out6
1
2
3
4
5
6
6
5
4
3
2
15riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > February > Platinum