BOJ 24973 - Up Down Subsequence
BOJ 24973 - Up Down Subsequence
풀이 1 - Segment Tree + DPPermalink
두 개의 세그먼트 트리를 관리하고 하나는 인덱스 에 인 것이 그 다음 문자가 일 때 가장 문자열에서 인덱스가 큰 것의 인덱스 를 저장하고 나머지 하나는 에 대해 저장한다.
그럼 이것 자체를 DP테이블로 쓸 수 있다.
- 자신이 첫 번째가 되는 경우
- 보다 작은 것 중 그 다음이 인 것중 가장 문자열에서 인덱스가 큰 것
- 보다 큰것 중 그 다음이 인 것 중 가장 문자열에서 인덱스가 큰 것
을 얻어와서 다시 세그먼트 트리에서 번째 값을 해서 DP값을 전이시켜주자.
에 풀 수 있다.
Comments