Изменения
→Пример задачи, решаемой методом convex hull trick
Рассмотрим задачу на ДП:
{{Задача
|definition = Есть n деревьев с высотами <tex>a1a_1, a2a_2, \dots ana_n</tex> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после
срубленного метра (любого дерева) пилу нужно заправлять, платя за бензин определенной кол-во монет. Причем стоимость
бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex>i</tex>, то цена заправки равна ci<tex>c_i</tex>. Изначально пила заправлена.Также известны следующие ограничения : <tex>c[n] c_n = 0, a[1] a_1 = 1, a[i]a_i</tex> возрастают, <tex>c[i]c_i</tex> убывают. Изначально пила заправлена.
(убывание и возрастание нестрогие)
}}
