본문 바로가기
알고리즘

BOJ 6171) 땅따먹기

by 박정률 2018. 5. 13.

어떤 땅의 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) 의 시간복잡도를 지닌다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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);
 
 
}
cs


'알고리즘' 카테고리의 다른 글

Usaco Gold) Fair Photography  (0) 2018.06.03
[기하] 다각형의 내부 외부 판별  (0) 2018.05.13
DP최적화 - Convex Hull Trick  (0) 2018.05.06
Sqrt Decompositon(평방분할) & Mo's Algorithm  (0) 2018.04.05
문자열 해싱  (0) 2018.03.31