Convex Hull Trick: когда и как применять для ДП вида dp[i] = min(dp[j] + a[j]·x[i])?
У меня ДП с переходом dp[i] = min over j<i of (dp[j] + b[j] * x[i]). Наивно это $O(n^2)$ — TLE. Слышал, что такой вид «линейных по x» переходов ускоряется «Convex Hull Trick». В чём идея и при каких условиях он применим?
2 ответа
Идея. Каждый кандидат j задаёт прямую y = b[j] * x + dp[j] (наклон b[j], сдвиг dp[j]). Тогда dp[i] = min по j от значения этих прямых в точке x = x[i]. Минимум по набору прямых в точке — это запрос к **нижней огибающей (lower envelope)** множества прямых. Поддерживая огибающую, отвечаем на запрос за $O(\log n)$ или $O(1)$ амортизированно вместо перебора всех j`.
Условия применимости (классический CHT):
- Наклоны
b[j]добавляются в монотонном порядке (тогда новую прямую кладём в конец, отсекая ставшие ненужными — стек/дек, $O(1)$ амортизированно на вставку). - Точки запросов
x[i]тоже монотонны — тогда указатель по огибающей двигается только вперёд, запрос $O(1)$ амортизированно.
Если оба монотонны — общая сложность $O(n)$. Если запросы произвольны — бинпоиск по огибающей, $O(n\log n)$. Если и наклоны произвольны — нужен Li Chao tree или динамический CHT (std::multiset), тоже $O(n\log n)$.
Итог: переход с $O(n^2)$ ужимается до $O(n)$ или $O(n\log n)$.
Минимальный скелет монотонного CHT на минимум (наклоны убывают, запросы возрастают):
struct Line { long long k, b; long long eval(long long x){ return k*x + b; } };
vector<Line> hull; int ptr = 0;
// плохая ли средняя прямая (можно убрать)?
bool bad(Line a, Line b, Line c){
// (c.b-a.b)*(a.k-b.k) <= (b.b-a.b)*(a.k-c.k) — пересечения
return (__int128)(c.b - a.b) * (a.k - b.k) <= (__int128)(b.b - a.b) * (a.k - c.k);
}
void add(long long k, long long b){
Line l{k, b};
while (hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), l)) hull.pop_back();
hull.push_back(l);
}
long long query(long long x){
if (ptr >= (int)hull.size()) ptr = hull.size()-1;
while (ptr + 1 < (int)hull.size() && hull[ptr+1].eval(x) <= hull[ptr].eval(x)) ++ptr;
return hull[ptr].eval(x);
}
Грабли: пересечения прямых считай в __int128 или через деление с осторожностью — k*x и разности сдвигов легко переполняют long long. И чётко определись, у тебя min или max огибающая — знаки неравенств в bad/query зеркальны. Если условия монотонности не выполняются — не мучайся с дек, бери Li Chao tree.