Материал из Викиконспекты
|
|
| Строка 1: |
Строка 1: |
| − | ==Наивное решение :== | + | ==первый заголовок== |
| − | Понятно, что нужно затратив минимальную стоимость срубить последнее (n-е) дерево, т.к. после него все деревья можно будет пилить бесплатно (т.к. c[n] = 0). Посчитаем следующую динамику : dp[i] - минимальная стоимость, заплатив которую будет срублено дерево номер i. Тогда dp[i] = min(dp[j] + a[i] * c[j]) по всем j < i. То есть понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешвые (док-во этого факта оставляется читателям как несложное упражнение). Тогда переберем j < i - индекс предыдущего срубленного дерева. Пусть мы его срубили отптимальным (в смысле денег) способом. Тогда просто a[i] раз уменьшим высоту дерева i на 1. Каждый такой раз будем платить c[j] за последующую заправку пилы. Итак, на сруб i-го дерева мы заплатили a[i]*c[j].
Нетрудно видеть, что такая динамика работает за <math>O(n^2)</math>.
| + | текст |
| | + | текст |
| | + | ==второй== |
| | + | текст текст |
Версия 18:57, 23 ноября 2016
первый заголовок
текст
текст
второй
текст текст
