Convex Hull Trick

일부 dp문제에서 시간복잡도를 획기적으로 줄여주는 걸로 유명한 테크닉입니다. 이번에 koi 2014 전국본선 3번으로 나왔으니 인지도가 더 올라갈 거 같네요.

개략적으로 설명하자면

문제를 풀다가 이런 형태의 점화식이 나올 때는 보통 n^2 말고는 희망이 없는데

이걸 이런 식으로 해석하면 기울기와 절편이 j에 따라 결정되는 형태의 일차함수들로 해석할수 있게 됩니다.

이러면 저러한 dp식을 구할때

(dp[0] = 0)

1. 0번 선분을 넣는다 (기울기 = b[0]. 절편 = dp[0])

2. 현재 들어간 선분 중 최솟값을 찾는다 (dp[1])

3. 1번 선분을 넣는다 (기울기 = b[1]. 절편 = dp[1])

4. 현재 들어간 선분 중 최솟값을 찾는다 (dp[2])

......

즉,

 * dp[i]를 구하고

 * 선분을 넣어주는

연산을 O(1)이나 O(lgn)에 할 수 있는 자료구조가 있으면 시간복잡도 향상을 꾀할 수 있습니다.

이 때 convex hull trick은 저 작업들을 모조리 O(lgn)만에 할 수 있습니다.

뿐만 아니라 a[i] < a[i+1]일 경우에는 O(1)만에 해버릴 수도 있습니다. (사실 스위핑이라서 정확히 O(1)은 아닙니다. 그냥 O(n/n)..)

달리 할말이 없네요... 나머지는 코드포스 어셉먹인 소스코드로 대체하겠습니다.

source code 

(저 문제의 점화식은 맨 위에 적어놓은 것과 똑같습니다. 상대적으로 쉬운 문제라서 그렇고 보통 약간의 변형을 거쳐야 저러한 점화식이 나오는 경우가 많습니다)

그 외에 연습할 수 있는 문제가 여럿 있으니 참고하세요

http://koistudy.net/?mid=prob_page&NO=355 (IOI 02 Batch Scheduling)

http://koistudy.net/?mid=prob_page&NO=2046 (USACO Gold Mar 08 Land Acquisition)

APIO'10 Commando

APIO'14 Sequence