Изменения
→Наивное решение
Понятно, что нужно затратив минимальную стоимость срубить последнее (<math>n</math>-е) дерево, т.к. после него все деревья можно будет пилить бесплатно (т.к. <math>c[n] = 0</math>). Посчитаем следующую динамику : <math>dp[i]</math> - минимальная стоимость, заплатив которую будет срублено дерево номер <math>i.</math> Тогда <math>dp[i] = min_{j=0...i-1}(dp[j] + a[i] * c[j])</math>. То есть понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение). Тогда переберем <math>j < i</math> - индекс предыдущего срубленного дерева. Пусть мы его срубили оптимальным (в смысле денег) способом. Тогда просто <math>a[i]</math> раз уменьшим высоту дерева i на 1. Каждый такой раз будем платить <math>c[j]</math> за последующую заправку пилы. Итак, на сруб <math>i</math>-го дерева мы заплатили <math>a[i]*c[j]</math>.
Нетрудно видеть, что такая динамика работает за <math>O(n^2)</math>
Посмотрим на код наивного решения:
''for''' i = 1..n-1 {
'''while''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font >
++pos
j = st[pos]
dp[i] = K[j] * a[i] + B[j]
'''if''' (i < n - 1) { <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font >
K[i] = c[i] <font color=green>// наши переобозначения переменных </font >
B[i] = dp[i] <font color=green>// наши переобозначения переменных </font >
x = -<tex>\infty</tex>
'''while''' (true) {
j = st[sz - 1]
x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font >
if (x > from[sz - 1]) '''break''' <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font >
--sz <font color=green>// удаляем последнюю прямую, если она лишняя </font >
}
st[sz] = i
from[sz++] = x <font color=green>// добавили новую прямую </font >
}
==О-Оптимизация==
