BOJ 6171) 땅따먹기

어떤 땅의 i 의 너비 Wi 와 Hi 가 주어진다.

이 때 가격은 Wi * Hi 이다.

- 한번에 여러개  된다면, (해당 땅 중 Wi의 최댓값 ) * (해당 땅 중 Hi의 최댓값)  으로 가격을 매긴다.

따라서 땅을 최소 비용으로 묶어서 살 경우 최소 비용은 ?

일단 무조건 wi를 기준으로 정렬을 시킨다.

이 때 만약 Wi 와 Hi 가 Wj , Hj보다 더 크다면 무조건 묶는게 이득이다. 

따라서 O(n) 시간으로 탐색하면서 더 큰 애들을 지워나간다.

그렇게 되면 현재 Wi 는 오름차순, Hi 는 내림차순으로 정렬된다.

 

그러고 DP를 생각해보자!

DP[i] = min (DP[j-1] + b[j] * a[i]) 의 식이 성립한다. ( b 는 내림차순)

그러므로 Convex Hull Trick 을 사용하면 된다.

이 때 순차적으로 DP[i] 값을 모두 구해나가야 한다.

따라서 O(n* logn) 의 시간복잡도를 지닌다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
typedef long long ll;
 
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);
    }
};
 
 
 
 
ll n;
pair<ll,ll> arr[50500];
 
 
int main(){
 
freopen("input.txt","r",stdin);
 
scanf("%lld",&n);
 
for(int i = 0 ; i < n ; i++){
    scanf("%lld %lld",&arr[i].first,&arr[i].second);
}
 
convex cv;
 
sort(arr,arr+n);
reverse(arr,arr+n);
 
ll now = -1;
ll prev = 0;
 
for(int i =0 ; i < n ; i++){
    if(now >= arr[i].second)    
        continue;
    now = arr[i].second;
    cv.add(arr[i].first,prev);
    prev = cv.query(arr[i].second);
}
 
 
printf("%lld",prev);
 
 
}