Изменения

Сначала заметим важный факт : т.к. c[i] убывают(нестрого) и c[n] = 0, то все c[i] неотрицательны.

Понятно, что нужно затратив минимальную стоимость срубить последнее (<math>n</math>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <math>c[n] = 0</math>). Посчитаем следующую динамику : <math>dp[i]</math> - минимальная стоимость, заплатив которую можно добиться того, что дерево номер <math>i.</math> будет срублено.

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

Итогвая формула пересчета : <math>dp[i] = min_{j=0...i-1}(dp[j] + a[i] * c[j])</math>. 


Посмотрим на код выше описанного решения:

dp[1] = 0

''for'' i = 1..n-1 {

dp[i] = +<tex>\infty</tex>