filot   4년 전

도저히 해결책이 생각 안나서 .. 정보올림피아드에서 풀이 내용을 봤는데

이 문제는, 먼저 기계의 식별 번호들을 단순화 시켜 순열(permutation)을 만든다.
예제에 나온 데이터로 예를 들자면, 윗 줄에 132 392 311 351 231이 나와 있고, 아래 줄
에 392 351 132 311 231이 나와 있는데, 윗줄의 132는 아랫줄의 3번째, 윗줄의 392는
아랫줄의 1번째 ... 와 같은 순서로 단순화시킬 수 있다.
예제로 나온 데이터에서의 순열은 3 1 4 2 5가 된다.
그다음 순열의 첫 번째부터 순서대로 보면서, 이전 순열에서 현재 순열 값보다 큰 값이 나
온 경우가 교차했다는 의미이므로, 이전 순열에서 자기보다 큰 값이 나온 횟수를 세야한다.


이렇게 되어 있길래 LIS를 유지하기 위해서 lower bound를 이용을 했습니다.

풀이에는 segment tree를 이용하라고 했지만

그래서 몇개의 테스트를 봤는데

5
569483 680496 157971 484174 256131 
680496 157971 569483 484174 256131 

위와 같은 경우 lower bound를 이용한 LIS를 할 경우 4가 나오는데..

실제로 전깃줄을 그려보면 2가 답입니다.


lower bound를 이용한 LIS가 원래 안되는건지... 설명해주실 분 있나요?


댓글을 작성하려면 로그인해야 합니다.