Изменения

Перейти к: навигация, поиск

Convex hull trick

13 байт добавлено, 01:13, 18 января 2017
Пример задачи, решаемой методом convex hull trick
Рассмотрим задачу на ДП:
{{Задача
|definition = Есть <math>n </math> деревьев с высотами <tex>a_1, a_2, \dots a_n</tex> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после
срубленного метра (любого дерева) пилу нужно заправлять, платя за бензин определенной кол-во монет. Причем стоимость
Анонимный участник

Навигация