백준 13263번: 나무 자르기

문제링크

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

13263번: 나무 자르기

풀이

• $dp[i]:$ i 번 나무를 완전히 자르는데 필요한 총 충전비용의 최솟값이라 하자
• $dp[i] = max_{0 <= j < i} (dp[j] + b[j] * a[i])$ 이다.
  • 이는 컨벡스헐트릭(Convex hull trick) 을 적용할 수 있는 점화식 형태이다.
• 또한 $b[N] = 0$ 이므로 $N$ 번 나무를 모두 자른 이후에는 충전비용이 0이 되고 이는 곧 문제의 답이 $dp[N]$ 임을 알 수 있다.

코드

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

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};

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

    int N;
    cin >> N;
    vector<long long> a(N), b(N);
    for (auto& e: a) {
        cin >> e;
    }
    for (auto& e: b) {
        cin >> e;
    }

    deque<line> dq;
    long long ans = 0;
    dq.push_front({b[0], 0});
    for (int i = 1; i < N; i++) {
        while (dq.size() >= 2 && dq[0].eval(a[i]) >= dq[1].eval(a[i]))
            dq.pop_front();
        ans = dq.front().eval(a[i]);
        line cur = {b[i], ans};
        while (dq.size() >= 2 && cur.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2]))
            dq.pop_back();
        dq.push_back(cur);
    }
    cout << ans << '\n';
}