DP최적화 - Convex Hull Trick

* 필요한 상황 

dp[i] = min( dp[j] + b[j]*a[i] ) 를 찾는건데 여기서 b[i] > b[i+1] ( b는 내림차순) 을 반드시 만족한다. (j < i 인 정수)

만약 오름차순이라면 굳이 계산할 필요가 없고, 내림차순이라면 binary search 로 찾을 수 있다.

이런 식이 나온다면 바로 CHT 를 쓸 수 있다.

여기서 문제가 되는 것은 바로 조건에 맞지 않는 직선들을 제거해주는 것이다.

* 업데이트

현재 line1이 새로 추가될 것이라고 생각하자.

그렇다면 line3 , line2 를 현재 저장된 라인들 중 가장 뒤에 있는 라인이라고 하자.

intersect - x(line3,line1) = x1

intersect - x(line3,line2) = x2 라고 해보자.

만약 x1 < x2 라고 한다면 이 직선은 이제 필요없다.

왜냐하면 이미 line3 다음에 line2가 그 다음으로 작아지기 시작하는건데

line3 다음에 이미 line1 이 더 작아졌으므로 애초에 line2는 들어올 필요가 없다.

그리고 라인 업데이트 같은 경우는 사실 이진탐색을 통해서 어디를 없애야하는 지 바로 알 수 있는 방법도 있다.

어차피 식을 보면 binary search를 통해서 충분히 찾을 수 있을 것으로 해석된다.

그런데 보통의 경우는 그렇게 사용되지 않고 O(1) amortized 시간복잡도를 갖게 된다.

* 쿼리 구하기

이제 직선들의 모임에서 x좌표가 어떤 직선에서 가장 최소값이 되는 지를 알아야 한다.

mid, mid+1 의 교점보다 x좌표가 더 작다면 mid 이하의 직선에서 최소값이 등장할 것이고

아니라면 mid+1 이상의 직선에서 최소값이 등장할 것이다.

line 별로 자기만의 최소값 구간이 있다고 보면 조금 편하다.

그렇다면 교점보다 x좌표가 더 작다면 최소값은 mid 이하의 점에서 나올것이 분명하다.

왜냐하면 이 친구의 mid+1 최소값 범위에는 x가 들어오지 않기 때문이다.

굉장히 쉽게 문제를 풀 수 있다.

* 예시문제 

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

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

http://www.spoj.com/problems/NKLEAVES/

http://codeforces.com/contest/311/problem/B

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

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

http://codeforces.com/contest/311/problem/B

http://codeforces.com/problemset/problem/377/E

어떤 경우에서도 항상 통하는 방법.
#define ll long long
 
struct convex{
    vector<ll> M;//기울기을 의미한다.
    vector<ll> B;//y절편의 값들
    //결국 조심해야될것은 이게 getval이나 bad가 long long 범위를 넘어서는지에 대한 거다
    bool bad(int l1,int l2,int l3){
        return (B[l3]-B[l1]*(M[l1]-M[l2]) < (B[l2]-B[l1])*(M[l1]-M[l3]));
    }
 
    double Cross(int a, int b) {
        return (double)(B[b] - B[a]) / (M[a] - M[b]);
    }
 
    void add(ll m,ll b){
        if(M.size()>0){
            if(M[M.size()-1]== m){
                B[M.size()-1]= min(B[M.size()-1],b);
            }
            else{
                M.push_back(m);
                B.push_back(b);
            }
        }
        else{
            M.push_back(m);
            B.push_back(b);
        }
 
        while(M.size()>=3 && Cross(M.size()-3,M.size()-2)> Cross(M.size()-2,M.size()-1) )
        {
            M.erase(M.end()-2);
            B.erase(B.end()-2);
        }
    }
 
    ll getval(ll x,int id){
        return B[id] + x*M[id];
    }
    ll query(ll x){
        int l = 0,r = M.size()-1,mid;
 
        while(l<r){
 
            mid = (l+r)/2;
            if(Cross(mid,mid+1)>=x)
                r = mid;
            else
                l = mid+1;
        }
        return getval(x,l);
    }
};
 
 
 
2. X가 증가형태로 주어지는 경우. O(1)으로 해결하는 방법.
 
struct convex{
    ll M[N],B[N];
    int sz,pos;
    double Cross(int a, int b) {
        return (double)(B[b] - B[a]) / (M[a] - M[b]);
    }
 
    void add(ll m,ll b){    
        M[sz] = m;
        B[sz++]= b;
 
        while(sz-pos>2&& Cross(sz-3,sz-2)> Cross(sz-2,sz-1) ){
            M[sz-2]= M[sz-1];
            B[sz-2]= B[sz-1];
            —sz;
        }
    }
 
    ll getval(ll x,int id){
        return B[id] + x*M[id];
    }
    ll query(ll x){
 
        while(pos+1<sz){
            if(Cross(pos,pos+1)<=x)++pos;
            else
                break;
        }
        return getval(x,pos);
    }
};