문제 링크
- https://icpc.me/27491
사용 알고리즘
- DP
- 세그먼트 트리
시간복잡도
- O(NlogN)
풀이
누적 합 배열을 이용하면 구간에 포함되 수들의 합이 0 이상이 되는지 빠르게 판별할 수 있습니다. Sr−Sl−1≥0인지 판별하면 되므로 Sr≥Sl−1인지 판별하면 됩니다.
점화식은 어렵지 않게 세울 수 있습니다. D(n) = \max\left{ D(n-1), D(i) + n - i \texttt{ when } 0 \leq i < n \land S_n \geq S_i \right}입니다. 단순하게 계산하면 O(N2)이고, 좌표 압축과 세그먼트 트리를 이용해 계산하면 O(NlogN) 시간에 점화식을 계산할 수 있습니다.
세그먼트 트리에서 해야 하는 연산이 prefix maximum query임을 관찰하면 세그먼트 트리 대신 펜윅 트리를 사용할 수도 있습니다. 아래 코드는 펜윅 트리를 사용한 코드입니다.
전체 코드
1 |
|