Изменения

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

Понятно, что нужно затратив минимальную стоимость срубить последнее (<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>