Изменения

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

Convex hull trick

Нет изменений в размере, 14:47, 5 января 2020
Пример задачи, решаемой методом 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>. Изначально пила заправлена.
Анонимный участник

Навигация