백준 6171번 땅따먹기

문제 요약

N개의 직사각형이 주어진다. 각 직사각형의 넓이는 $W_i * H_i$로 주어집니다.

각 직사각형의 가격은 $W_i*H_i$가 됩니다. 이 때, 여러 개의 땅을 묶어서 살 때는 묶음의 가격이 $(maxW_i) * (maxH_i)$가 됩니다.

이 때, 모든 땅을 살 수 있는 최소의 비용을 구하는게 목적이다.

풀이

묶음으로 살 때 가격을 정하는 방식 때문에 $W_i \ge W_j$이고 $H_i \ge H_j$면 j번째 땅은 무시할 수 있습니다.

이러한 전처리는 $W$의 오름차순으로 땅을 정렬한 뒤에 순서대로 보면서 지워질 대상을 지워나가면 전부 지울 수 있습니다.

각 땅을 $H$의 내림차순이면서 $W$는 오름차순인 상태로 만들 수 있습니다.

이러한 전처리가 끝난 상태의 땅들에 대해서 다음과 같은 dp식을 생각합시다.
$$
\begin{aligned}
dp(i) &= \text{1번부터 i번 땅까지 샀을 때의 최소비용} \\
dp(i) &= \underset{j<i}{min}(h_{j+1}*W_i + dp(j))
\end{aligned}
$$
이는 Convex Hull Trick으로 처리 가능합니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1e10;
int N;
pll a[50005], b[50005];
ll dp[50005];
int ptr;
struct Line {
    ll m, b;
    double x;
    Line(ll _m, ll _b, double _x) : m(_m), b(_b), x(_x) {};
    ll f(ll x) {
        return m * x + b;
    }
};
vector<Line> lines;

double intersect(Line& a, Line& b) {
    return (double)(b.b - a.b) / (a.m - b.m);
}

void addLine(ll m, ll b) {
    Line a(m, b, -INF);
    if (lines.empty()) {
        lines.push_back(a);
        return;
    }
    while (!lines.empty()) {
        Line top = lines.back();
        double x = intersect(top, a);
        if (x <= top.x) lines.pop_back();
        else break;
    }
    a.x = intersect(lines.back(), a);
    lines.push_back(a);
    if (ptr >= lines.size()) ptr = lines.size() - 1;
    return;
}

ll query(ll x) {
    while (ptr < lines.size() - 1 && lines[ptr + 1].x < x) ++ptr;
    return lines[ptr].f(x);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> a[i].first >> a[i].second;
    sort(a, a + N);
    int idx = 0;
    for (int i = 0; i < N; ++i) {
        while (idx > 0 && b[idx - 1].second <= a[i].second) --idx;
        b[idx++] = a[i];
    }
    N = idx;
    addLine(b[0].second, 0);
    for (int i = 0; i < N - 1; ++i) {
        dp[i] = query(b[i].first);
        addLine(b[i + 1].second, dp[i]);
    }
    cout << query(b[N - 1].first) << '\n';
    return 0;
}