Изменения

Сначала заметим важный факт : т.к. <tex>c[i] </tex> убывают(нестрого) и <tex>c[n] = 0</tex>, то все <tex>c[i] </tex> неотрицательны.Понятно, что нужно затратив минимальную стоимость срубить последнее (<mathtex>n</mathtex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <mathtex>c[n] = 0</mathtex>). Посчитаем следующую динамику : <mathtex>dp[i]</mathtex> - минимальная стоимость, заплатив которую можно добиться того, что дерево номер <mathtex>i.</mathtex> будет срублено. База динамики : <mathtex>dp[1] = 0</mathtex>, т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи.Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед <mathtex>i</mathtex>-м деревом мы обязательно срубили какое-то <mathtex>j</mathtex>-е, причем <mathtex>j < i</mathtex>. Поэтому чтобы найти <mathtex>dp[i]</mathtex> нужно перебрать все <mathtex>1 <= j < i</mathtex> и попытаться использовать ответ для дерева намер <mathtex>j</mathtex>. Итак, пусть перед <mathtex>i</mathtex>-м деревом мы полностью срубили <mathtex>j</mathtex>-е, причем высота <mathtex>i</mathtex>-го дерева составляет <mathtex>a[i]</mathtex>, а т.к. последнее дерево, которое мы срубили имеет индекс <mathtex>j</mathtex>, то стоимость каждого метра <mathtex>i</mathtex>-го дерева составит <mathtex>c[j]</mathtex>. Поэтому на сруб <mathtex>i</mathtex>-го дерева мы потратим <mathtex>a[i] * c[j]</mathtex> монет. Также не стоит забывать, ситуацию, когда <mathtex>j</mathtex>-е дерево полностью срублено, мы получили не бесплатно, а за <mathtex>dp[j]</mathtex> монет.Итогвая формула пересчета : <mathtex>dp[i] = min_{j=0...i-1}(dp[j] + a[i] * c[j])</mathtex>. 
 

dp[1] = 0 dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex> ''for'' i = 1..n-1 { dp[i] = +<tex>\infty</tex> ''for'' j = 0..i-1 { ''if'' (dp[j] + a[i] * c[j] < dp[i]) dp[i] = dp[j] + a[i] * c[j] } }Нетрудно видеть, что такая динамика работает за <mathtex>O(n^2)</mathtex>.