Сегодня обсудим одну из самых краисвых техник в алгоритмическом программировании. Convex Hull Trick - это техника оптимизации динамического программирования, которая по сути пришла из методов оптимизаций, она помогает быстрее находить лучший вариант среди множества линейных функций.
Идея здесь достаточно простая: иногда в DP для каждого состояния нужно перебрать все предыдущие состояния и выбрать минимум или максимум. Из-за этого решение может работать слишком медленно - например, за квадрат. Convex Hull Trick позволяет посмотреть на такие переходы иначе: каждое предыдущее состояние можно представить как прямую, а новый запрос — как точку, в которой нужно найти самую выгодную прямую. Главная идея в том, что не все прямые действительно нужны. Некоторые из них никогда не дадут лучший ответ, поэтому их можно спокойно выбросить. Оставшиеся прямые образуют «оболочку», по которой уже можно быстро искать ответ.
Когда это работает?
CHT обычно подходит, если переход в DP можно привести к виду:
dp[i] = лучший ответ среди выражений вида:
k[j] * x[i] + b[j]
То есть каждое предыдущее состояние j превращается в прямую:
y = k * x + b
А для текущего i мы спрашиваем: какая прямая даёт минимум или максимум в точке x[i]?
Геометрический смысл
В геометрическом смысле CHT - это хранение нижней огибающей всех прямых. Каждое предыдущее состояние DP задаёт некоторую прямую. Но не все прямые важны: если прямая нигде не является минимальной, она никогда не повлияет на ответ, и её можно удалить. В итоге мы храним только те прямые, которые хотя бы на каком-то промежутке дают лучший ответ. Эти прямые и образуют нижнюю огибающую. Запрос в точке x - это просто поиск прямой на этой огибающей, которая находится ниже всех остальных в этой точке.
Псевдокод
Этот вариант работает, если прямые добавляются в отсортированном порядке по наклону, а запросы по x идут монотонно.
hull = empty deque
function bad(line1, line2, line3):
return line2 никогда не будет лучше,
чем line1 или line3
function add_line(k, b):
new_line = (k, b)
while hull.size >= 2 and bad(hull[-2], hull[-1], new_line):
удалить последнюю прямую из hull
добавить new_line в конец hull
function get(x):
while hull.size >= 2 and value(hull[0], x) >= value(hull[1], x):
удалить первую прямую из hull
return value(hull[0], x)
function value(line, x):
return line.k * x + line.b
Для максимума знак сравнения в get нужно поменять и строить верхнюю огибающую. Если порядок добавления прямых или порядок запросов произвольный, обычный deque уже может не подойти. В таком случае часто используют Li Chao Tree.
Практика
CSES — Monster Game I
CSES — Monster Game II
CSES — Subarray Squares
AtCoder DP Contest — Z. Frog 3
Codeforces — 1083E. The Fair Nut and Rectangles
Здесь можно почитать более подробно про эту структуру
@postupashki_prog