Изменения
→Пример задачи, решаемой методом convex hull trick
==Пример задачи, решаемой методом convex hull trick==
Рассмотрим задачу на ДП:
Есть n деревьев с высотами <mathtex>a1, a2, \dots an</mathtex> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после
срубленного метра (любого дерева) пилу нужно заправлять, платя за бензин определенной кол-во монет. Причем стоимость
бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки
равна ci. Изначально пила заправлена.
Также известны следующие ограничения : <mathtex>c[n] = 0, a[1] = 1, a[i]</mathtex> возрастают, <mathtex>c[i]</mathtex> убывают. Изначально пила заправлена.
(убывание и возрастание нестрогие)
(Задача H отсюда : http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf)
