Изменения

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

Теперь формула приняла вид <math>dp[i] = min_{j=0...i-1}(k[j]*x[i] + b[j])</math>. Выражение <math>k[j]*x + b[j]</math> напоминает уравнение прямой <math>y = kx + b</math>. Сопоставим каждому <math>j</math>, обработанному ранее прямую <math>y[j](x) = k[j]*x + b[j]</math>. Из условия «<math>c[i]</math> убывают <math><=> k[j]</math> уменьшаются с номером <math>j</math>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коеффицентакоэффициент. Давайте нарисуем несколько таких прямых :

Итак, давайте выделим множество точек <math>(x0, y0)</math> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <math>y’(x)</math>, такой что <math>y’(x0) < y0</math>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых. На катинке картинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функцию. Назовем ее «<math>y = convex(x)</math>»

Пусть мы считаем динамику для <math>i</math>-го дерева. Его задает <math>x[i]</math>. Итак, нам нужно для данного <math>x[i]</math> найти минимум по всем <math>min_{j=0..i-1}(k[j]*x[i] + b[i]) = min_{j=0..i-1}(y[j](x[i]))</math>. Нетрудно видеть, что это есть convex(x[i]). Из монотонности угловых коеффицентов коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую <math>x = x[i]</math>, можно найти бинарным поиском. Это потребует O(logn) времени на поиск такого j, что dp[i] = k[j] * x[i] + b[j]. Теперь осталось научиться быстро поддерживать множество прямых и добавлять <math>i</math>-ю прямую после того, как мы посчитали <math>b[i] = dp[i]</math>. Название статьи подсказывает, что нужно воспользоваться алгоритмом построения выпуклой оболочки множества точек. Но (внезапно) у нас не точки, а прямые… Но что меняется??? Пусть есть 2 стека <math>k[] и b[]</math>, которые задают прямые в отсортированном порядке. Пусть пришла новая прямая. Найдем точки пересечения (по x) с последними 2мя прямыми из стека. Назовем их <math>xL</math> и <math>xR</math>. Если оказалось, что новая прямая пересекает предпосл еднюю предпоследнюю прямую выпуклой оболочки позже, чем последнюю (xL >= xR), то последнюю можно удалить из нашего множества. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2 или <math>xL</math> не станет меньше <math>xR.</math> Ассимптотика Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно 1 раз добавится в стек и максимум 1 раз удалится. Значит время работы перестройки выпуклой оболочки займет <math>O(n)</math> суммарно.

Т.е. нужно уметь быстро (за <math>O(logn)</math>?) назодить, после какой прямой стоит пытаться вставить текущую (красную рис.4) примую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте хранить <math>std::set</math> (или любой аналог в других языках) пар <math><k, st></math> = <коеффицент коэффицент прямой, ее номер в глобальной нумерации>. Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую прямую с меньшим углом наклона, и начиная с нее повторяем старый алгоритм (удаляем, пока прямая бесполезная). И симметричный алгоритм применяем ко всем прямым справа от нашей. Ассимптотика Асимптотика решения составит <math>O(logn)</math> на каждый из n запросов «добавить прямую» + <math>O(n)</math> суммарно на удаление прямых. Итго <math>O(nlogn)</math>.

Ассимптотика Асимптотика алгоритма по-прежнему составит <math>O(n*log(n))</math>