실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
수찬은 그가 키우는 강아지들 사이에서 품종이 우호적일 경우 일부 품종 간의 상호작용이 된다는 사실을 알게 되는데, 이는 품종 ID 측면에서 쉽게 특성화할 수 있습니다.
품종 a와 b는 |a-b| ≤ 4이면 우호적이고, 그렇지 않으면 비우호적입니다. 서로 우호적인 품종들이라면, 다른 품종이 지정된 영역으로 돌아다니는 것은 괜찮습니다.
수찬의 농장을 지나는 도로 양측의 N 개의 영역이 순서대로 주어졌을 때 (양쪽에 각 품종에 대해 정확히 하나의 영역이 있음) 횡단보도 두 개가 교차하지 않고, 각 횡단보도가 우호적인 두 품종이 포함된 한 쌍의 영역과 연결되도록 존이 자신의 도로 위에 그릴 수 있는 최대 '횡단보도' 수를 결정하도록 도와주세요.
각 영역은 최대 하나의 횡단보도를 통해서만 접근할 수 있습니다.(따라서 횡단보도의 끝점이 만나지 않도록 하세요.)
첫 번째 입력 줄에는 N (1 ≤ N ≤ 100,000)이 포함됩니다. 다음 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, Platinum Problem 2. Why Did the Cow Cross the Road II