Изменения
→Ключевая идея оптимизации
1) Сделаем замену обозначений. Давайте обозначим <tex>dp[j]</tex> за <tex>b[j]</tex>, <tex>a[i]</tex> за <tex>x[i]</tex>, а <tex>c[j]</tex> за <tex>k[j]</tex>.
2) Теперь формула приняла вид <tex>dp[i] = min_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><=> k[j]</tex> уменьшаются с номером <tex>j</tex>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :
