컨벡스 헐 트릭

어떤 DP를 가속하나

다음 꼴의 점화식을 생각하자.

$$ dp[i] = \min_{j < i} \big( dp[j] + b[j] \cdot a[i] \big) + (\text{$i$만의 항}) $$

각 \(j\)는 기울기 \(b[j]\), 절편 \(dp[j]\)인 직선 \(y = b[j] x + dp[j]\)를 정의하고,
\(dp[i]\)는 그 직선들을 \(x = a[i]\)에서 평가한 최솟값에 해당한다. 직선이 \(N\)개,
질의가 \(N\)개이므로 단순히 하면 \(O(N^2)\)인데, 컨벡스 헐 트릭(CHT) 은 이를
\(O(N \log N)\) 또는 \(O(N)\)으로 줄인다.

핵심: 하부 포락선

여러 직선의 점별 최솟값을 모으면 아래로 볼록한 조각별 선형 함수(하부
포락선, lower envelope)가 된다. 어떤 직선은 모든 \(x\)에서 다른 직선들에 가려
절대 최솟값이 되지 않는데, 그런 직선은 버려도 된다. 남는 직선들만 기울기 순으로
정렬해 두면, 각 직선이 최솟값이 되는 구간이 연속으로 나뉜다.

직선 세 개 \(\ell_1, \ell_2, \ell_3\)(기울기 증가 순)에서, \(\ell_2\)가 \(\ell_1\)과
\(\ell_3\)의 교점보다 위에 있으면 \(\ell_2\)는 항상 가려져 불필요하다.
이 "가운데가 위로 튀면 버린다"는 판정이 볼록 껍질을 만드는 것과 같다.

단조 CHT (스택, \(O(N)\))

추가되는 직선의 기울기가 단조(증가 또는 감소)이고, 질의 \(x\)도 단조라면
스택으로 \(O(1)\) 분할상환에 처리한다.

1. 직선을 기울기 순으로 push하되, 위 판정으로 가운데가 불필요해지면 pop.
2. 질의 \(x\)가 단조 증가면, 스택 앞쪽에서 "다음 직선이 더 낫다"가 될 때까지
   포인터를 전진시키며 답을 읽는다.

총 push/pop과 포인터 이동이 각각 \(O(N)\)이라 전체 선형이다.

일반 CHT (\(O(\log N)\) 질의)

질의 \(x\)가 단조가 아니면, 포락선 위에서 이분 탐색으로 해당 구간의 직선을
찾는다. 직선 추가가 기울기 순이면 여전히 스택을 쓰되 질의만 이분 탐색해
\(O(\log N)\). 추가 순서까지 임의면 리 차오 트리나 셋 기반 동적 CHT가
필요하다(이후 주제).

최댓값 버전

최댓값을 구하려면 상부 포락선을 쓰면 된다. 부등호와 판정 방향을 모두 뒤집고,
직선의 기울기를 음수로 바꿔 최솟값 코드를 재사용하는 트릭도 흔하다.

단조 CHT 스택 구현 (최솟값)

기울기가 감소 순으로 들어오고 질의가 증가 순인 전형적 경우다. 교점 비교는
부동소수 대신 정수 곱으로 한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct CHT {
    vector<ll> m, b;          // 직선 y = m*x + b
    int ptr = 0;

    // l3 추가 시 가운데 직선 l2가 불필요한가? (정수 비교)
    bool bad(int l1, int l2, int l3) {
        // (b[l3]-b[l1])/(m[l1]-m[l3]) <= (b[l2]-b[l1])/(m[l1]-m[l2])
        return (long double)(b[l3] - b[l1]) * (m[l1] - m[l2])
             <= (long double)(b[l2] - b[l1]) * (m[l1] - m[l3]);
    }
    void add(ll slope, ll intercept) {   // 기울기 감소 순으로 호출
        m.push_back(slope); b.push_back(intercept);
        int sz = m.size();
        while (sz >= 3 && bad(sz - 3, sz - 2, sz - 1)) {
            m.erase(m.end() - 2);        // 가운데 제거
            b.erase(b.end() - 2);
            sz--;
        }
    }
    ll query(ll x) {                     // 질의 x 증가 순
        if (ptr >= (int)m.size()) ptr = m.size() - 1;
        while (ptr + 1 < (int)m.size() &&
               m[ptr + 1] * x + b[ptr + 1] <= m[ptr] * x + b[ptr])
            ptr++;                       // 다음 직선이 더 작으면 전진
        return m[ptr] * x + b[ptr];
    }
};

질의가 단조가 아니면 query에서 포인터 대신 이분 탐색으로 최적 직선을 찾으면
된다.

흔한 실수

• 부동소수 교점 — 교점을 double로 비교하면 정밀도 문제로 틀린다. 위처럼
  교차 곱(정수) 으로 비교하라.
• 단조성 가정 위반 — 기울기나 질의가 단조가 아닌데 스택+포인터를 쓰면
  오답이다. 가정을 반드시 확인하고, 깨지면 이분 탐색이나 리 차오 트리로 가자.
• 최소/최대 혼동 — 최댓값을 원하면 판정 부등호와 정렬 방향을 모두 뒤집어야
  한다.
• 오버플로 — m * x가 큰 값이면 long long도 넘을 수 있다. 범위를 미리
  추정하자.

적용 예: 분할 비용 DP

대표 문제는 "막대를 \(K\) 부분으로 잘라 비용을 최소화"처럼

$$ dp[i] = \min_{j} \big( dp[j] + (s[i] - s[j])^2 \big) $$

꼴인데, 전개하면 \(-2\ s[j]\)를 기울기, \(dp[j] + s[j]^2\)를 절편으로 하는 직선들의
\(x = s[i]\) 평가가 된다. 누적합 \(s\)가 단조 증가하므로 단조 CHT로 \(O(N)\)에
풀린다.

기울기·질의가 모두 임의 순서면 리 차오 트리, 결정 단조성이 있으면 분할
정복 최적화가 대안이다. CHT는 "DP 전이에 곱 항이 섞일 때"를 알아보는 안목이
가장 중요하다.