L. Распил брусьев

Брус длиной $L$ надо распилить в заданных местах. Распил бруска длиной $k$ стоит $k$ рублей независимо от того, где именно пилят. Найдите наименьшую суммарную стоимость.

Пример из условия: брус длиной 10, распилы на 2, 4 и 7. Если пилить по порядку 2, 4, 7 - это $10 + 8 + 6 = 24$. Если сначала на 4, потом 2, потом 7 - $10 + 4 + 6 = 20$.

Состояние

Добавим к списку распилов концы бруса: $c_0 = 0$ и $c_{N+1} = L$. Тогда любой кусок в процессе работы - это отрезок между двумя точками из этого списка.

$dp[i][j]$ - стоимость распила куска от $c_i$ до $c_j$ по всем внутренним точкам. Перебираем, какой распил делается первым:

Слагаемое $c_j - c_i$ - это цена первого распила: он всегда делается по целому куску, какой бы точки ни касался. База: $dp[i][i+1] = 0$, внутри резать нечего.

Это ровно та же схема, что в задаче про склейку куч, только «снаружи внутрь», а не «изнутри наружу». Полезно заметить, что $\min$ и слагаемое поменялись местами по сравнению с умножением матриц: там цена зависела от точки разреза, тут - нет.

$O(N^3)$ при $N \le 100$ - миллион операций.

Про жадность

Соблазн пилить всегда посередине силён, и на примере из условия он даже срабатывает. Но это не общее правило: постройте набор из двух распилов, на котором «посередине» проигрывает, - это полезнее, чем прочитать про это здесь.

Подробнее: «Динамика по подотрезкам».

В первой строке - числа $L$ и $N$ ($2 \le L \le 10^6$, $1 \le N \le 100$) - длина бруса и количество распилов.

Во второй строке - $N$ чисел $C_i$ ($0 < C_i < L$) в строго возрастающем порядке.

Одно число - наименьшая стоимость распила.