凸包优化(CHT)

What · 是什么

凸包优化（Convex Hull Trick, CHT / 斜率优化）是 DP 优化技术：当转移形如 dp[i] = min_j (k_j * x_i + b_j) + C_i 时，把每个决策 j 看成平面上的直线 y = k_j*x + b_j（或点 (k_j, b_j)），则 dp[i] 是在 x = x_i 处所有直线的最低点。若插入的斜率单调（或 x_i 单调），可用单调队列在均摊 O(1) 维护下凸壳并在 O(1)/O(log n) 内查询；若都不单调，可用动态开点李超线段树或平衡树。它是斜率优化 DP 的最主流实现之一，典型例题为「HNOI2008」玩具装箱。

Why · 为什么

How · 实现

伪代码

# 维护 min, 要求插入斜率严格单调（此处示例: 递减），查询 x 递增
class CHT:
    m, b = [], []        # 直线 y = m[k]*x + b[k], m 递减
    ptr = 0
    def bad(l1, l2, l3):  # l2 是否冗余
        return (b[l3]-b[l1])*(m[l1]-m[l2]) <= (b[l2]-b[l1])*(m[l1]-m[l3])
    def add(nm, nb):
        m.append(nm); b.append(nb)
        while len(m) >= 3 and bad(len(m)-3, len(m)-2, len(m)-1):
            删除倒数第二条
    def query(x):
        while ptr+1 < len(m) and m[ptr]*x+b[ptr] >= m[ptr+1]*x+b[ptr+1]:
            ptr += 1
        return m[ptr]*x + b[ptr]

Python 实现

# -*- coding: utf-8 -*-


class CHT:
    """下凸壳，求 min。要求插入斜率严格单调；
    若查询 x 单调递增，用单调指针 O(1)；否则用二分 O(log n)。
    """
    def __init__(self):
        self.m = []   # 斜率，严格递减
        self.b = []
        self.ptr = 0

    def _bad(self, l1, l2, l3):
        return (self.b[l3] - self.b[l1]) * (self.m[l1] - self.m[l2]) <= \
               (self.b[l2] - self.b[l1]) * (self.m[l1] - self.m[l3])

    def add(self, k, b):
        self.m.append(k)
        self.b.append(b)
        while len(self.m) >= 3 and self._bad(len(self.m)-3, len(self.m)-2, len(self.m)-1):
            self.m.pop(-2)
            self.b.pop(-2)

    def _f(self, i, x):
        return self.m[i] * x + self.b[i]

    def query(self, x):
        while self.ptr + 1 < len(self.m) and self._f(self.ptr, x) >= self._f(self.ptr + 1, x):
            self.ptr += 1
        return self._f(self.ptr, x)


def cht_query_binary(lines, x):
    """二分查询版：不要求 x 单调。lines 为按斜率递减排序的直线列表。"""
    lo, hi = 0, len(lines) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        k1, b1 = lines[mid]
        k2, b2 = lines[mid + 1]
        # 两直线交点 x = (b2-b1)/(k1-k2)
        if (b2 - b1) / (k1 - k2) <= x:
            lo = mid + 1
        else:
            hi = mid
    k, b = lines[lo]
    return k * x + b


if __name__ == '__main__':
    lines = [(1, 5), (2, 1), (3, -2), (4, 0)]  # 斜率递增
    cht = CHT()
    for k, b in reversed(lines):               # 插入需要斜率递减
        cht.add(k, b)
    for x in range(-3, 6):
        bf = min(k*x + b for k, b in lines)
        assert abs(cht.query(x) - bf) < 1e-9, (x, cht.query(x), bf)
    # 二分查询版（任意 x 顺序）
    hull = cht.m and sorted(list(zip(cht.m, cht.b)), key=lambda t: -t[0]) or []
    for x in [10, -5, 0, 3]:
        bf = min(k*x + b for k, b in lines)
        assert abs(cht_query_binary(hull, x) - bf) < 1e-9, (x, cht_query_binary(hull, x), bf)
    print('convex-hull-trick all tests passed')

易错点

• 斜率插入方向与查询单调性必须与维护的凸壳类型匹配（增/减、min/max）
• 斜率相等时先合并，只保留截距较优的直线
• bad 判据的叉积符号随斜率单调方向翻转，写反会丢直线
• 查询 x 非单调时不能用单调指针，要用二分/李超树
• 浮点溢出/精度：大整数时用分数比较或 __int128 思路（Python 大整数天然安全）
• DP 初始决策（j=0）必须作为第一条直线先加入

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/geometry/convex_hull_trick.html
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/dp/opt/slope.md
• 书籍✓ CPH ch28