Распил бревна
Бревно длиной L сантиметров нужно распилить в отмеченных местах. Лесопилка берёт за каждый распил столько тенге, сколько сантиметров в куске, который пилят: кусок целиком протаскивают через станок. Порядок распилов выбираете вы. Сколько заплатить меньше всего?
Например, бревно в 10 см с отметками 2, 4 и 7 можно пилить слева направо: 10 + 8 + 6 = 24 тенге. А если начать с 4, то 10 + 4 + 6 = 20.
Вход
В первой строке — L и n (2 ≤ L ≤ 106, 1 ≤ n ≤ 150). Во второй — n различных отметок в порядке возрастания, каждая строго между 0 и L.
Выход
Одно число — наименьшая плата в тенге.
Примеры
Пример 1
10 3 2 4 7
20
Пример 2
100 6 25 50 51 52 53 54
191
Ограничения
- Время · Python
- 2000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Посмотрите на самый первый распил. После него два куска распиливаются независимо друг от друга. Какие задачи остались и чем они похожи на исходную?
2Подсказка 2
Кусок между отметками i и j — тоже бревно со своими отметками. Сколько стоит его первый распил, где бы он ни был?
3Идея
Добавим к отметкам концы бревна: x0 = 0, xn+1 = L. cost[i][j] — наименьшая плата за все распилы внутри куска от xi до xj. Первый распил этого куска где-то в отметке k, i < k < j, стоит xj − xi при любом k, и дальше куски [i, k] и [k, j] распиливаются отдельно: cost[i][j] = xj − xi + mink(cost[i][k] + cost[k][j]). Это динамика на отрезках.
4Разбор
Отрезки считаем по возрастанию длины: каждый опирается только на более короткие. Куски без отметок внутри стоят ноль. Ответ — cost[0][n + 1].
Во втором примере бревно в 100 см с отметками 25, 50, 51, 52, 53, 54. Отметка ближе всего к середине — 50, и пилить с неё кажется разумным: 208 тенге. Лучше начать с 54: тогда пять близких отметок оказываются на коротком куске длиной 54 см, а длинный хвост в 46 см больше не пилят. Получается 191.
4+Решение
5Сложность
Отрезков O(n²), у каждого O(n) вариантов первого распила: O(n³) времени, O(n²) памяти. При n = 150 — около шестисот тысяч шагов. Для больших n помогает наблюдение Кнута: лучшая отметка для [i, j] лежит между лучшими для [i, j − 1] и [i + 1, j], и время падает до O(n²) — подробнее в статье об оптимизациях динамики.
6Типичные ошибки
- Пилить посередине. Не проходит второй пример: центральная отметка не обязательно лучшая.
- Пилить по порядку слева направо. Платится за длинный остаток снова и снова: в первом примере 24 вместо 20.
- Отрезки в неправильном порядке. Если считать cost[i][j] по возрастанию i, то cost[k][j] для k > i ещё не готово; нужен порядок по длине или i по убыванию.