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