Изменения
→О-Оптимизация
==О-Оптимизация==
Давайте обозначим <math>dp[j] </math> за <math>b[j]</math>, <math>а[i] </math> за <math>x[i]</math>, а <math>c[j] </math> за <math>k[j]</math>.Теперь формула приняла вид <math>dp[i] = minmin_{j=0...i-1}(k[j]*x[i] + b[j]) по всем j < i/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>. Из условия «c«<math>c[i] </math> убывают <math><=> k[j] </math> уменьшаются с номером j» <math>j</math>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффицента. Давайте нарисуем несколько таких прямых :
///картинка 1
Итак, давайте выделим множество точек <math>(x0, y0) </math> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <math>y’(x)</math>, такой что <math>y’(x0) < y0</math>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых. На катинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функцию. Назовем ее «y «<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>.
