Изменения

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

2) Теперь формула приняла вид <mathtex>dp[i] = min_{j=0...i-1}(k[j]*x[i] + b[j])</mathtex>. Выражение <mathtex>k[j]*x + b[j]</mathtex> - это в точности уравнение прямой вида <mathtex>y = kx + b</mathtex>.

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

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