Convex Hull Trick

Convex Hull Trick은 DP의 시간 복잡도를 획기적으로 줄일 수 있는 방법으로, DP optimization의 세가지 종류 중 하나이다. CHT조아

 

$dp(i) = min_{j<i}( A(i)B(j) + C(i) + D(j) )$ 꼴의 점화식이 나왔을 때 사용한다.

 

$dp(i) = min_{j<i}( A(i)B(j) + D(j) ) + C(i)$ ( $B(j)$는 단조성 )

$dp(i) = max_{j<i}( A(i)B(j) + D(j) ) + C(i)$ ( $B(j)$는 단조성 )

 

$f(x) = B(j) x + D(j)$ 일 때 $x=A(i)$ 를 대입

 

각 식을 위 일차함수식으로 생각하면, f(x) 에 A(i) 를 대입하여 최솟값을 구하면 된다.

이를 위하여 위 그림에서의 아래쪽의 convex hull을 생각하자.

struct Line { ll a, b; };

double cross(const Line &p, const Line &q) { return (double)(q.b-p.b)/(p.a-q.a); }

vector<Line> S;

void update(Line p)
{
    while(S.size()>1 && cross(S[S.size()-1], p)<=cross(S[S.size()-1], S[S.size()-2])) S.pop_back();
    S.push_back(p);
}

ll query1(ll x)
{
    int lo=0, hi=S.size();
    while(lo+1<hi)
    {
        int mid=lo+hi>>1;
        if(cross(S[mid], S[mid-1])<=x) lo=mid;
        else hi=mid;
    }
    return S[lo].a*x+S[lo].b;
}

int pos=0;
ll query2(ll x)
{
    if(S.size()<=pos) pos=S.size()-1;
    else while(pos+1<S.size() && cross(S[pos+1], S[pos])<=x) pos++;
    return S[pos].a*x+S[pos].b;
}

 

왼쪽부터 오른쪽으로 일차함수들을 스택에 넣어 관리하자.

cross 함수는 두 선분이 교차하는 점의 x축 위치를 반환한다. 이때 이 함수의 형이 Double 형인데, 오차를 막기 위해서는 별도의 유리수 struct Frac 을 선언해 준 후, 유리수 간의 비교 연산자를 정의해 주면 된다.

 

1. update

스택 상의 마지막 직선과 그 전 직선과의 교점 P, 마지막 직선과 그 전 직선과의 교점 Q를 계산한다.

마지막 직선 다음에 지금 추가할 직선이 쌓이려면 Q가 P보다 x좌표가 커야 한다. 즉, 이게 만족하지 않는다면 계속 스택에서 빼준다.

 

2. query1 ($NlogN$)

첫번째 방법은 별다른 조건이 없을 때 이진탐색을 이용하는 것이다.

각 선에 대하여 그 직선이 원하는 x좌표와 겹치는 직선이려면, 그 직선이 전 직선과 겹치는 점의 x좌표($cross(S[mid], S[mid-1])$)는 원하는 x좌표보다 작아야 한다.

이를 이용하여 이분탐색을 통해 답을 구할 수 있다.

 

3. query2 ($N$)

이 방법은 $A(i)$ 가 증가할 때 $(A(i)<=A(i+1))$ 일때 사용할 수 있는 방법이다.

이분탐색할 필요 없이 다음 직선의 x좌표($cross(S[pos], S[pos+1])$)가 원하는 x좌표보다 작을 때까지 계속 반복하면 된다.

 

https://www.acmicpc.net/problem/13263

https://www.acmicpc.net/problem/17168

https://www.acmicpc.net/problem/6171

https://www.acmicpc.net/problem/4008