# [Diamond V] 땅따먹기 [문제 링크](https://www.acmicpc.net/problem/6171) ## 문제 설명 <p>농부 상헌이는 선재의 부동산에서 N개의 땅을 모두 사려고 한다. 땅은 W_i * H_i 크기의 직사각형으로 생각할 수 있다.</p> <p>선재는 그동안 땅 하나의 가격을 W_i * H_i로 매겨서 팔았는데, 사실 요즘 선재는 장사가 잘 안 된다. 손님이 급한 선재는 다음과 같은 묶음 할인 행사를 통해서 땅을 팔고 있다.</p> <ul> <li>여러 개의 땅을 살 때는, (해당 땅 중 W_i의 최댓값) * (해당 땅 중 H_i의 최댓값) 으로 가격을 매긴다.</li> </ul> <p>상헌이는 선재의 행사가 매우 좋다고 생각해서 땅을 살 준비를 하고 있었지만, 땅을 어떻게 묶어사는지에 따라 가격이 천차만별이라는 사실을 깨닫게 되었다! 상헌이가 최소 비용으로 땅을 묶어서 살 경우, 최소 비용은 얼마일까?</p> ## 입력 <p>첫 번째 줄에 N이 주어진다. (1 <= N <= 50000)</p> <p>이후 N개의 줄에 W_i, H_i가 주어진다. (1 <= W_i, H_i <= 1000000)</p> ## 출력 <p>상헌이가 땅을 사는 최소 비용을 출력하라.</p> ## 풀이 dp[i]를 i번 땅까지 가격을 지불할 때의 최소 비용으로 두고 풀었습니다. W 내림차순, H 내림차순으로 정렬하면, i가 증가하는데 H가 감소하면, 그 땅은 바로 앞 땅에 끼워 팔면 비용이 들지 않는다. 이러한 땅들을 전부 제외하면 dp[i] = min($W_{j+1}$$H_i$ + dp[j]) 꼴이 나와 이를 CHT로 최적화하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[50'001]; struct element { ll a, b; double x=0; }; struct block { ll w=0, h=0; bool operator<(const block b) const { if(w!=b.w) return w>b.w; return h>b.h; } }; double meetX(element a, element b) { return (double)(a.b-b.b)/(b.a-a.a); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<block> v(n); for(int i=0;i<n;i++) cin >> v[i].w >> v[i].h; sort(v.begin(), v.end()); vector<block> merged(1); for(int i=0;i<n;i++) { if(!merged.empty() && merged.back().h>=v[i].h) continue; merged.push_back(v[i]); } vector<element> stk; for(int i=1;i<merged.size();i++) { element cur = {merged[i].w, dp[i-1]}; while(!stk.empty()) { cur.x = meetX(stk.back(), cur); if(cur.x>stk.back().x) break; stk.pop_back(); } stk.push_back(cur); int left=0, right=stk.size()-1; while(left<right) { int mid = left+right+1>>1; if(merged[i].h<stk[mid].x) right=mid-1; else left=mid; } dp[i] = stk[left].a*merged[i].h + stk[left].b; } cout << dp[merged.size()-1]; } ```