跳轉到

Convex Hull Trick

Convex Hull Trick，常稱為斜率優化，適合處理可以整理成以下形式的 DP：

\[ dp[j] = c[j] + \min_i (m_i x_j + b_i) \]

也就是每個轉移來源 i 都能變成一條直線，查詢 j 時只需要在 x_j 找到最小值。若直線斜率加入順序單調，且查詢的 x 也單調，就可以用 deque 維護 lower hull，讓每次加線和查詢都是 amortized O(1)。

Monotonic CHT

這份模板維護最小值查詢：

  • add(m, b)：加入直線 y = m * x + b。
  • bad(a, b, c)：判斷中間的線 b 是否永遠不會成為最優解。
  • query(x)：查詢目前所有直線在 x 的最小值。

時間複雜度

  • 加入直線：amortized O(1)
  • 查詢最小值：amortized O(1)
  • DP 轉移：若原本是 O(k n^2)，在單調條件成立時可降為 O(k n)

使用條件

  • 這份模板對應「斜率遞減、查詢 x 遞增」的最小值查詢。
  • 查詢的 x 要單調，才能在 query 時從 deque 前端 pop。
  • 若斜率是遞增方向，可以調整 bad 的判斷式，或把加入線的順序反過來。
  • 若斜率或查詢順序不單調，通常要改用 Li Chao tree，或在 hull 上二分查詢。
  • 乘法可能溢位時，交叉相乘建議使用 __int128_t。

模板

C++
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128_t;

struct Line {
    i128 m, b;

    Line(i128 m = 0, i128 b = 0) : m(m), b(b) {}

    i128 get(i128 x) const {
        return m * x + b;
    }
};

class CHT {
public:
    deque<Line> dq;

    bool empty() const {
        return dq.empty();
    }

    bool bad(const Line& a, const Line& b, const Line& c) {
        return (b.b - a.b) * (b.m - c.m)
            >= (c.b - b.b) * (a.m - b.m);
    }

    void add(i128 m, i128 b) {
        Line cur(m, b);

        if (!dq.empty() && dq.back().m == cur.m) {
            if (dq.back().b <= cur.b) return;
            dq.pop_back();
        }

        while (dq.size() >= 2 && bad(dq[dq.size() - 2], dq[dq.size() - 1], cur)) {
            dq.pop_back();
        }

        dq.push_back(cur);
    }

    i128 query(i128 x) {
        while (dq.size() >= 2 && dq[0].get(x) >= dq[1].get(x)) {
            dq.pop_front();
        }

        return dq[0].get(x);
    }
};

DP 轉換

以 LeetCode - Minimum Partition Score 為例，假設 pf[i] 是 prefix sum。若最後一段是 (p + 1) .. j，令：

\[ x = pf[j], \quad y = pf[p] \]

區間和為 x - y，score 是：

\[ \frac{(x - y)(x - y + 1)}{2} \]

因此轉移可以寫成：

\[ dp[t][j] = \min_p \left( dp[t - 1][p] + \frac{(pf[j] - pf[p])(pf[j] - pf[p] + 1)}{2} \right) \]

展開後：

\[ dp[t][j] = \frac{x^2 + x}{2} + \min_p \left( -pf[p] \cdot x + dp[t - 1][p] + \frac{pf[p]^2 - pf[p]}{2} \right) \]

對固定的 p 來說，括號內就是一條直線：

  • slope：m = -pf[p]
  • intercept：b = dp[t - 1][p] + (pf[p] * pf[p] - pf[p]) / 2
  • query point：x = pf[j]

所以每一層 t 都可以邊掃 j、邊把可用的 p = j - 1 加進 CHT，再查詢 pf[j] 的最小值。

參考題型

  • LeetCode - Minimum Partition Score：把 partition DP 的轉移展開成直線查詢。因為 prefix sum 單調，加入的 slope 和查詢的 x 都單調，可以使用 deque CHT。
C++
class Solution {
public:
    using ll = long long;
    using i128 = __int128_t;

    long long minPartitionScore(vector<int>& nums, int k) {
        int n = nums.size();
        vector<i128> pf(n + 1, 0);

        for (int i = 0; i < n; ++i) {
            pf[i + 1] = pf[i] + nums[i];
        }

        const i128 INF = (i128)1 << 120;
        vector<vector<i128>> dp(k + 1, vector<i128>(n + 1, INF));
        dp[0][0] = 0;

        for (int t = 1; t <= k; ++t) {
            CHT cht;

            for (int j = 1; j <= n; ++j) {
                int p = j - 1;

                if (dp[t - 1][p] < INF / 2) {
                    i128 x = pf[p];
                    i128 m = -x;
                    i128 b = dp[t - 1][p] + (x * x - x) / 2;

                    cht.add(m, b);
                }

                if (!cht.empty()) {
                    i128 x = pf[j];
                    dp[t][j] = (x * x + x) / 2 + cht.query(x);
                }
            }
        }

        return (ll)dp[k][n];
    }
};