Изменения
→Пример задачи, решаемой методом convex hull trick
|definition = Есть <math>n</math> деревьев с высотами <tex>a_1, a_2, \dots, a_n</tex> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
бензопилы. Но пила устроена так, что она может спиливать только по <math>1</math> метру от дерева, к которому ее применили. Также после
срубленного метра (любого дерева) пилу нужно заправлять, платя за бензин определенной определенное кол-во монет. Причем стоимость
бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex>i</tex>, то цена заправки
равна <tex>c_i</tex>. Изначально пила заправлена.
[[Файл:picture1convexhull.png]]
Выделим множество точек <tex>(x_0, y_0)</tex> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <tex>y’(x)</tex>, такой что <tex>y’(x_0) < y_0</tex>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней ошибающей огибающей множества прямых на плоскости). Назовем ее «<tex>y = convex(x)</tex>». Видно, что множество точек <math>(x, convex(x))</math> представляет собой выпуклую вверх функцию.
==Цель нижней огибающей множества прямых==
'''int''' <tex>\mathtt{ConvexHullTrick}</tex>('''int''' a[n], '''int''' c[n])
st[1] = 1
sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>
pos = 1 <font color=green>// текущая позиция первого такого j, что x[i] \geqslant front[st[j]] </font >
sz = sz - 1<font color=green>// удаляем последнюю прямую, если она лишняя </font >
st[sz + 1] = i
sz = sz + 1
'''return''' dp[n]
