백준 6171번: 땅따먹기

문제링크

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

6171번: 땅따먹기

풀이

• 자신의 w, h 보다 모두 큰 땅이 존재하면 그 땅은 그 큰 땅에 포함하여 사면 비용을 들이지 않고 사기 가능
• 그러한 땅들을 모두 제외하면 w 오름차순으로 정렬했을 때 h 는 내림차순으로 정렬됨
• i 번 땅과 j 번 땅을 같이 묶어서 사면, 그 사이에 있는 땅들은 포함해도 추가 비용 들지 않음
  • i번 땅과 묶인 땅들의 비용 = w[i] * h[j] 이므로
• 따라서, $dp[i]:$ i 번 땅까지 사는데 필요한 최소 비용이라고 정의하면
• $dp[i] = min_{0 \leq j < i} (dp[j] + w[i] * h[j + 1]) $
  • CHT 적용
    • x: 증가
    • 기울기: 감소
    • getMin

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()

struct line {
    long long m, c;
    long long eval(long long x) {return m * x + c;}
    long long intersecX(line l) {return (c - l.c) / (l.m - m);}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<pair<long long, long long> > v(N);

    for (int i = 0; i < N; ++i) {
        cin >> v[i].first >> v[i].second;
    }

    sort(all(v));

    vector<pair<long long, long long> > v2;

    long long prevMax = v.back().second;
    v2.push_back(v.back());
    for (int i = N - 2; i >= 0; --i) {
        if (v[i].second > prevMax) {
            v2.push_back(v[i]);
            prevMax = v[i].second;
        }
    }

    reverse(all(v2));

    deque<line> dq;
    long long ans = 0;
    dq.push_back({v2[0].second, 0});
    for (int i = 0; i < v2.size(); ++i) {
        while (dq.size() >= 2 && dq[0].eval(v2[i].first) >= dq[1].eval(v2[i].first)) dq.pop_front();
        ans = dq.front().eval(v2[i].first);
        ans = dq.front().eval(v2[i].first);
        if (i == v2.size() - 1) break;
        line cur = {v2[i + 1].second, ans};
        while (dq.size() >= 2 && cur.intersecX(dq.back()) <= dq.back().intersecX(dq[dq.size() - 2])) dq.pop_back();
        dq.push_back(cur);
    }

    cout << ans << '\n';
}