Задача E. "Ну-ка, покатились!"
Рассмотрим решение с помощью метода динамического программирования.Пусть Di - минимальный штраф, который мы заплатим, если будем решать задачу для шариков с номерами от i до n, причем шарик номер i будет обязательно приколот.
Тогда
где
![](https://espresso.codeforces.com/83da3a38385341cb229379fa7881e37f76ad555d.png)
Если числа S(i, j) не считать каждый раз, а пересчитывать, используя формулу S(i, j) = S(i, j - 1) + xj - xi, то решение требует всего O(n) памяти и O(n2) времени на решение.
Важное замечание: в приведенных рассуждениях, шарики нужно рассматривать в порядке увеличения их координат.