Изменения

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

Convex hull trick

63 байта добавлено, 19:37, 23 ноября 2016
Постановка примера задачи
Есть n деревьев с высотами <math>a1, a2, … an</math>. Требуется спилить их все, потратив минимальное количество монет на заправку бензопилы. Но пила устроена так, что после уменьшения высоты спиливаемого дерева на 1 ее надо заправить. Причем стоимость заправки зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки равна ci. Изначально пила заправлена.
И известны следующие ограничения : <math>c[n] = 0, a[1] = 1, a[i]</math> возрастают, <math>c[i]</math> убывают.
(Задача с codeforcesH отсюда : http://neerc.comifmo.ru/school/camp-2016/problems/20160318a.pdf)
==Наивное решение==
Анонимный участник

Навигация