Идея

Нужно выполнить все распилы в некотором порядке и минимизировать общую стоимость.

Цена одного распила равна длине текущего куска, который мы режем. Значит, если сначала резать большой кусок, это дорого, но иногда без этого нельзя добраться до нужных внутренних распилов.

Ключевая идея: рассматривать не весь процесс целиком, а отдельные отрезки палки между соседними важными точками. Для каждого такого отрезка будем считать минимальную стоимость, чтобы выполнить все распилы внутри него.

Это приводит к интервальной динамике.

Наблюдения

Добавим к списку точек две границы:

• 0 — начало палки,
• L — конец палки.

Пусть после сортировки получился массив pts.

Теперь любая задача сводится к такому вопросу:

• какова минимальная стоимость распилить кусок от pts[i] до pts[j], если нужно сделать все распилы, лежащие строго между ними?

Обозначим ответ как dp[i][j].

Что происходит при первом распиле внутри отрезка

Если на отрезке (pts[i], pts[j]) есть хотя бы один обязательный распил, то какой-то из них будет выполнен первым. Пусть это точка pts[m], где i < m < j.

Тогда:

• сначала платим pts[j] - pts[i] за распил текущего куска целиком;
• после этого задача разбивается на две независимые:
  • распилить левую часть от pts[i] до pts[m],
  • распилить правую часть от pts[m] до pts[j].

Значит,

dp[i][j] = min(dp[i][m] + dp[m][j] + (pts[j] - pts[i])) по всем m между i и j.

База

Если между i и j нет ни одной точки распила, то ничего делать не нужно, значит:

• dp[i][j] = 0.

Это как раз случаи, когда j = i + 1.

Алгоритм

1. Считать L, k и все позиции распилов.
2. Сформировать массив точек:
   • добавить 0,
   • добавить все распилы,
   • добавить L,
   • отсортировать.
3. Создать таблицу dp размера n x n, где n — число всех точек вместе с границами.
4. Заполнять dp по возрастанию длины интервала:
   • рассматриваем все пары i, j, где j = i + len;
   • перебираем первую точку распила m между ними;
   • обновляем минимум.
5. Ответом будет dp[0][n - 1].

Почему это работает

Докажем, что динамика действительно находит минимальную стоимость.

Рассмотрим произвольный отрезок от pts[i] до pts[j].

Случай 1: внутри нет распилов

Тогда делать ничего не нужно, стоимость равна 0. Именно это и хранит dp[i][j].

Случай 2: внутри есть распилы

В любом допустимом порядке некоторый распил будет первым. Пусть он делается в точке pts[m].

Стоимость этого первого действия неизбежно равна длине текущего куска, то есть pts[j] - pts[i].

После первого распила отрезок распадается на две части:

• от pts[i] до pts[m],
• от pts[m] до pts[j].

Все дальнейшие распилы в левой части никак не влияют на правую, и наоборот. Значит, минимальная стоимость после выбора первого распила равна

dp[i][m] + dp[m][j].

Тогда общая стоимость при первом распиле в m:

dp[i][m] + dp[m][j] + (pts[j] - pts[i]).

Так как первый распил можно выбрать по-разному, нужно взять минимум по всем возможным m.

Именно это делает переход динамики.

Почему порядок вычисления корректен

Значение dp[i][j] использует только значения для меньших интервалов:

• dp[i][m],
• dp[m][j].

Поэтому если заполнять таблицу по возрастанию длины интервала, все нужные значения уже будут посчитаны.

Следовательно, алгоритм корректно вычисляет минимальную стоимость для всех интервалов, а значит и для всей палки.

Сложность

Пусть всего точек n = k + 2.

• Состояний в динамике: O(n^2).
• Для каждого состояния перебираем m, то есть до O(n) вариантов.

Итоговая сложность:

• O(n^3), то есть O(k^3).

По памяти:

• O(n^2).

При k <= 100 это легко проходит.

Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    long long L;
    cin >> L;

    int k;
    cin >> k;

    vector<long long> pts;
    pts.push_back(0);

    for (int i = 0; i < k; i++) {
        long long x;
        cin >> x;
        pts.push_back(x);
    }

    pts.push_back(L);
    sort(pts.begin(), pts.end());

    int n = (int)pts.size();
    vector<vector<long long>> dp(n, vector<long long>(n, 0));

    for (int len = 2; len < n; len++) {
        for (int i = 0; i + len < n; i++) {
            int j = i + len;
            long long best = -1;

            for (int m = i + 1; m < j; m++) {
                long long cur = dp[i][m] + dp[m][j] + (pts[j] - pts[i]);
                if (best == -1 || cur < best) {
                    best = cur;
                }
            }

            if (best == -1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = best;
            }
        }
    }

    cout << dp[0][n - 1] << "\n";
    return 0;
}

Код на Python 3

L = int(input())
k = int(input())
cuts = list(map(int, input().split()))

pts = [0] + sorted(cuts) + [L]
n = len(pts)

dp = [[0] * n for _ in range(n)]

for length in range(2, n):
    for i in range(n - length):
        j = i + length
        best = None
        segment_len = pts[j] - pts[i]
        for m in range(i + 1, j):
            cur = dp[i][m] + dp[m][j] + segment_len
            if best is None or cur < best:
                best = cur
        if best is not None:
            dp[i][j] = best

print(dp[0][n - 1])