Изменения

Перед началом решения Сначала заметим важный факт, напрямую следующий из условия : т.к. c[i] убывают(нестрого) и c[n] = 0, то все c[i] не отрицательнынеотрицательны. Понятно, что нужно затратив минимальную стоимость срубить последнее (<math>n</math>-е) дерево, т.к. после него все деревья можно будет пилить рубить бесплатно (т.к. <math>c[n] = 0</math>). Посчитаем следующую динамику : <math>dp[i]</math> - минимальная стоимость, заплатив которую будет срублено можно добиться того, что дерево номер <math>i.</math> Тогда <math>будет срублено. База динамики : dp[i1] = min_{j=0, т.к..i-изначально пила заправлена и высота первого дерева равна 1}(dp[j] + a[i] * c[j])</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>-го дерева i на 1. Каждый такой раз будем платить составит <math>c[j]</math> за последующую заправку пилы. Итак, Поэтому на сруб <math>i</math>-го дерева мы заплатили потратим <math>a[i]*c[j]</math>монет. 
Нетрудно видетьТакже не стоит забывать, что такая динамика работает ситуацию, когда <math>j</math>-е дерево полностью срублено, мы получили не бесплатно, а за <math>Odp[j]</math> монет.Итогвая формула пересчета : <math>dp[i] = min_{j=0...i-1}(n^2dp[j] + a[i] * c[j])</math>. 
Посмотрим на код наивного выше описанного решения: dp[1] = 0 dp[2] = dp[3] = ... = dp[n] = <tex>infty</tex>