Изменения
→Наивное решение
Понятно, что нужно затратив минимальную стоимость срубить последнее (<tex>n</tex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <tex>c[n] = 0</tex>). Посчитаем следующую динамику : <tex>dp[i]</tex> - минимальная стоимость, заплатив которую можно добиться того, что дерево номер <tex>i.</tex> будет срублено.
База динамики : <tex>dp[1] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи.
Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед <tex>i</tex>-м деревом мы обязательно срубили какое-то <tex>j</tex>-е, причем <tex>j < i</tex>. Поэтому чтобы найти <tex>dp[i]</tex> нужно перебрать все <tex>1 \leqslant j < i</tex> и попытаться использовать ответ для дерева намер <tex>j</tex>. Итак, пусть перед <tex>i</tex>-м деревом мы полностью срубили <tex>j</tex>-е, причем высота <tex>i</tex>-го дерева составляет <tex>a[i]</tex>, а т.к. последнее дерево, которое мы срубили имеет индекс <tex>j</tex>, то стоимость каждого метра <tex>i</tex>-го дерева составит <tex>c[j]</tex>. Поэтому на сруб <tex>i</tex>-го дерева мы потратим <tex>a[i] <tex>\cdot </tex> c[j]</tex> монет. Также не стоит забывать, ситуацию, когда <tex>j</tex>-е дерево полностью срублено, мы получили не бесплатно, а за <tex>dp[j]</tex> монет.Итогвая формула пересчета : <tex>dp[i] = \min\limits_{j=1...i-1} (dp[j] + a[i] <tex>\cdot </tex> c[j])</tex>.
Посмотрим на код выше описанного решения:
'''int''' simple-dp('''int''' a[], '''int''' c[], '''int''' n) 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] <tex>\cdot </tex> c[j] < dp[i]) dp[i] = dp[j] + a[i] <tex>\cdot </tex> c[j]
}
} '''return''' dp[n]
Нетрудно видеть, что такая динамика работает за <tex>O(n^2)</tex>.
