Изменения

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

Convex hull trick

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

Навигация