BOJ 24973 - Up Down Subsequence

BOJ 24973 - Up Down Subsequence

풀이 1 - Segment Tree + DP

두 개의 세그먼트 트리를 관리하고 하나는 인덱스 $i$에 $p_i=i$ 인 것이 그 다음 문자가 $U$ 일 때 가장 문자열에서 인덱스가 큰 것의 인덱스 를 저장하고 나머지 하나는 $D$ 에 대해 저장한다.

그럼 이것 자체를 DP테이블로 쓸 수 있다.

• $p_i$ 자신이 첫 번째가 되는 경우
• $p_i$ 보다 작은 것 중 그 다음이 $U$ 인 것중 가장 문자열에서 인덱스가 큰 것
• $p_i$ 보다 큰것 중 그 다음이 $D$ 인 것 중 가장 문자열에서 인덱스가 큰 것

을 얻어와서 다시 세그먼트 트리에서 $p_i$ 번째 값을 $+1$ 해서 DP값을 전이시켜주자.

$O(n \log n)$에 풀 수 있다.

풀이 2 - LIS

정해 링크