Convex Hull Trick(CHT)

CHT로 불리는 그냥 DP최적화 기법이다.

Convex Hull Trick 알고리즘은 직선의 집합에서 주어진
x 값에 대해 가장 낮거나 가장 높은 y 값을 효율적으로 찾는 데 사용됨.

이 알고리즘의 핵심 아이디어는 효율적으로 쿼리를 처리하기 위해 직선들을 "볼록 껍질"(convex hull) 특히 위로볼록 구조에 유지하는 것

구현

#include <iostream>
#include <deque>
using namespace std;

struct Line {
    long long a, b;
    double start; // 교점의 x 좌표

    Line(long long a = 0, long long b = 0, double start = -1e18) : a(a), b(b), start(start) {}

    long long value(long long x) const {
        return a*x + b;
    }

    double intersect(const Line& other) const {
        return (double)(other.b - b) / (a - other.a);
    }
};

class ConvexHullTrick {
private:
    deque<Line> hull;

public:
    void add_line(long long a, long long b) {
        Line newLine(a, b);
        while (hull.size() >= 2 && newLine.intersect(hull[0]) >= hull[0].intersect(hull[1])) {
            hull.pop_front();
        }
        hull.push_front(newLine);
    }

    long long query(long long x) {
        while (hull.size() >= 2 && hull.back().value(x) >= hull[hull.size() - 2].value(x)) {
            hull.pop_back();
        }
        return hull.back().value(x);
    }
};

대표 문제

백준 13263 나무자르기

dp[i] = i번째 나무까지의 최소 시간.
점화식 : dp[i] = min(dp[j] + b[j] * a[i]) (0<=j<i)중 최소값. 여기서 점화식 형태가 선형적이면 CHT적용 가능.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

struct Line {
    long long a, b;
    double start;

    Line(long long a = 0, long long b = 0, double start = -1e18) : a(a), b(b), start(start) {}

    long long value(long long x) const {
        return a * x + b;
    }

    double intersect(const Line& other) const {
        return (double)(other.b - b) / (a - other.a);
    }
};

class ConvexHullTrick {
private:
    deque<Line> hull;

public:
    void add_line(long long a, long long b) {
        Line newLine(a, b);
        while (hull.size() >= 2 && newLine.intersect(hull[0]) >= hull[0].intersect(hull[1])) {
            hull.pop_front();
        }
        hull.push_front(newLine);
    }

    long long query(long long x) {
        while (hull.size() >= 2 && hull.back().value(x) >= hull[hull.size() - 2].value(x)) {
            hull.pop_back();
        }
        return hull.back().value(x);
    }
};

int main() {
    int N;
    scanf("%d", &N);

    vector<long long> a(N + 1), b(N + 1), dp(N + 1);
    for (int i = 1; i <= N; ++i) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= N; ++i) {
        scanf("%lld", &b[i]);
    }

    ConvexHullTrick cht;
    cht.add_line(b[1], 0); // 처음에는 첫번째 나무를 심는 것만 고려

    for (int i = 2; i <= N; ++i) {
        dp[i] = cht.query(a[i]);
        cht.add_line(b[i], dp[i]);
    }

    printf("%lld\n", dp[N]);
    return 0;
}

웬만하면 cout cin 대신 scanf, printf사용 하는게 낫다.