Изменения

==Ключевая идея оптимизации==

1) Сделаем замену обозначений. Давайте обозначим <math>dp[j]</math> за <math>b[j]</math>, <math>a[i]</math> за <math>x[i]</math>, а <math>c[j]</math> за <math>k[j]</math>.

2) Теперь формула приняла вид <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>.

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