백준 13263번 나무 자르기

문제 요약

나무 N개의 높이가 주어집니다. 각 나무의 높이가 $a_i$입니다. 전기톱을 한 번 사용하면 특정 나무의 높이를 1 줄이는 것이 가능합니다.

전기톱을 충전하는 비용은 현재 완전히 잘려진 나무의 번호 중 최댓값에 따라 결정 되는데 이 값을 $b_i$라고 합니다.

이 때, 모든 나무를 자르는 데에 필요한 최소 비용을 구해야 합니다. $a_1=1$은 보장됩니다.

풀이

일단 완전히 잘린 나무가 없으면 충전이 불가능하므로 $a_1$을 제일 처음자릅니다. 그리고 $b_N=0$이기 때문에 N번 나무를 자르면 그 뒤의 충전 비용은 0이 됩니다. 심지어 $b_i > b_j, (i<j)$이기 때문에 고민할 거는 나무의 번호가 큰 나무를 먼저 자르고 이전 거를 자를지 정하는 것입니다.

이 점을 고려해보기 위해서 dp식을 세웁시다
$$
\begin{aligned}
dp(i) &= \text{i번 나무를 높이 1로 만드는 최소 비용} \\
dp(i) &= \underset{j<i}{min}(b_ja_i+dp(j))
\end{aligned}
$$
이를 이용하면 $dp(N)$이 우리가 원하는 최소 비용이 됩니다.

Convex Hull Trick을 이용하면 해당 값을 $O(N^2)$가 아닌 $O(NlogN)$ 혹은 $O(N)$에 구할 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1e10;
int N;
ll a[100005], b[100005], dp[100005];
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];
    for (int i = 0; i < N; ++i) cin >> b[i];
    dp[0] = 0; addLine(b[0], dp[0]);
    for (int i = 1; i < N; ++i) {
        dp[i] = query(a[i]);
        addLine(b[i], dp[i]);
    }
    cout << dp[N - 1] << '\n';
    return 0;
}