S가 정수의 수열이라고 할 때, LIS(최장 증가 부분수열)이란 S에서 몇 개의 원소를 제거한 다음, 나오게 되는 부분수열이 오름차순(작은 순서에서 큰 순서대로, 같은 건 존재하지 않는다.)으로 나오는 부분수열 중 가장 긴 수열을 말한다.

예를 들어 S={1, 3, 2, 7, 3, 6}의 LIS={1, 2, 3, 6}이 된다.

A와 B의 정수의 수열이 주어질 경우, 2개를 합쳐서 LIS를 구해보고자 한다. 여기서 2개의 수열을 합친다는 것은 하나의 수열이 자리잡은 상태에서 다른 수열의 원소들이 그 사이사이에 배치하는 것을 말한다. 추가되는 수열의 하나의 원소는 자리잡은 수열에 한번만 들어갈 수 있으며, 어디에 들어가도 상관없으나, 원래의 순서가 바뀌어서는 안 된다. 다시 말해서 2개의 수열을 합칠때는 각 수열의 원소끼리는 원래의 순서를 유지하면서 두 수열의 원소를 임의의 위치에 배치할 수 있다는 말이다.

만약 {2, 1}, {3, 4} 라는 두개의 수열이 있을 경우 {3, 4, 2, 1}은 합친 부분 수열이 될 수 있으며, {1, 3, 4} 역시 가능하나, {1, 2, 3, 4}의 경우 불가능하다.

합친 부분 수열의 LIS를 구해보자.

#1388 upload 355 done 58 how_to_reg 40

합친 부분 수열의 LIS timer 1s memory 64MB

#1388

합친 부분 수열의 LIS 1s 64MB