| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 111 | 76 | 68 | 73.913% |
1ドル$ 이상 $n$ 이하 정수들로 이루어진 길이 $n$인 순열 $A$와 $B$가 주어진다. $A$와 $B$에서 동일한 $k − 1$개의위치를 골라서 각각 $k$개의 조각으로 나누려고 한다. 단, 각 $i = 1, 2, \dots , k$에 대해, $A$의 $i$번째 조각의 최솟값의 위치와 $B$의 $i$번째 조각의 최솟값의 위치가 서로 같아야 한다. 예를 들어서, $A =(1, 3, 2, 5, 4)$ 이고 $B = (5, 4, 3, 2, 1)$라 하자. 만약, $A$를 $(1), (3, 2), (5, 4)$로 나누면, $B$는 $(5), (4, 3), (2, 1)$로 나누어지며, 위에서 설명한 조건을 만족시킨다. 물론 $A$와 $B$를 길이가 1ドル$인 $n$개의 조각들로 나누면 위 조건을 쉽게 만족시킬 수 있다. 따라서 우리는 조건을 만족하면서 조각의 수 $k$가 최소가 되도록 나누고자 하며, 이러한 분할을 최적의 분할이라고 하자. 위 예시에서 $k = 3$인 분할이 최적의 분할이다.
$n,ドル $A,ドル $B$가 주어질 때, 최적의 분할을 찾고, 그 때의 $k$를 출력하는 프로그램을 작성하시오.
입력은 표준입력을 사용한다. 첫 줄에 $A$와 $B$의 길이를 나타내는 양의 정수 $n$ (1ドル ≤ n ≤ 3,000円$)이 주어진다. 두 번째 줄에 $A$에 대한 정보가 주어지며, 1ドル$ 이상 $n$ 이하인 $n$개의 정수들이 주어진다. 세번째 줄에 $B$에 대한 정보가 주어지며, 1ドル$ 이상 $n$ 이하인 $n$개의 정수들이 주어진다. 두 번째 줄과 세번째 줄에서, 같은 줄에는 같은 정수가 두 번 이상 주어지지 않는다.
출력은 표준출력을 사용한다. 첫 줄에 최적의 분할의 조각 수를 출력한다.
5 1 3 2 5 4 5 4 3 2 1
3
5 1 2 3 4 5 1 5 4 3 2
1
5 1 2 3 4 5 5 4 3 2 1
5