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