Convex hull trick

Материал из Викиконспекты
Версия от 18:45, 23 ноября 2016; 92.255.113.52 (обсуждение) (Наивное решение :)
Перейти к: навигация, поиск

Наивное решение :

Понятно, что нужно затратив минимальную стоимость срубить последнее (n-е) дерево, т.к. после него все деревья можно будет пилить бесплатно (т.к. c[n] = 0). Посчитаем следующую динамику : dp[i] - минимальная стоимость, заплатив которую будет срублено дерево номер i. Тогда dp[i] = min(dp[j] + a[i] * c[j]) по всем j < i. То есть понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешвые (док-во этого факта оставляется читателям как несложное упражнение). Тогда переберем j < i - индекс предыдущего срубленного дерева. Пусть мы его срубили отптимальным (в смысле денег) способом. Тогда просто a[i] раз уменьшим высоту дерева i на 1. Каждый такой раз будем платить c[j] за последующую заправку пилы. Итак, на сруб i-го дерева мы заплатили a[i]*c[j]. 
Нетрудно видеть, что такая динамика работает за [math]O(n^2)[/math].