실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
대학의 연구실에서 한 교수가 N(1 ≤ N ≤ 1000) 종류의 식물을 키우고 있으며, 각각을 1에서 N까지 번호로 매겼습니다. 일부 식물 종류 간에는 다른 종류보다 더 친밀한 상호작용을 가지고 있는데,, 식물 ID를 기준으로 다음과 같이 쉽게 특성화됩니다: 종류 a와 종류 b가 친밀하면 |a−b| ≤ 4이고, 그렇지 않으면 친밀하지 않습니다.
대학의 연구실에는 긴 복도가 있습니다. 복도의 한쪽에는 N개의 연구실이 있으며 (각 식물 종류별로 한 개에 대응), 복도의 반대편에도 N개의 연구실이 있습니다. (역시 각 식물 종류별로 한 개에 대응). 식물들을 안전하게 한 연구실에서 다른 연구실로 이동시키기위해 복도에 안전한 통로를 만드려 합니다. 각 통로는 복도의 한 쪽에 있는 연구실과 복도 반대편의 연구실를 연결해야 하며, 두 연구실의 식물 ID가 친밀한 경우에만 가능합니다. (식물들이 다른 종류의 식물이 위치한 연구실로 들어가는 것은 괜찮지만, 친밀한 종이어야 합니다). 각 연구실은 최대 하나의 통로를 통해 접근할 수 있습니다 (통로는 그 끝점에서 만나지 않아야 합니다).
대학의 연구실 복도 양끝에 있는 N개의 연구실 순서가 주어졌을 때, 교수님이 겹치지 않는 최대 통로의 수를 계산하는 것을 도와주세요.
입력의 첫 번째 줄에는 N이 주어집니다. 다음 N개의 줄에는 도로 한쪽에 있는 연구실의 식물 ID 순서를 설명합니다. 각 식물 ID는 1부터 N까지의 정수 범위 안에 있습니다. 마지막 N개의 줄에는 다른 한쪽 도로에 있는 연구실의 식물 ID 순서를 설명합니다. 각 식물 ID는 각각 한 번씩만 나타납니다.
교수가 복도를 가로지르는 최대 겹치지 않는 "친밀한 통로"의 수를 출력해 주세요.
6 1 2 3 4 5 6 6 5 4 3 2 1
5
출처: USACO 2017 February Contest, Gold Problem 2. Why Did the Cow Cross the Road II