CS
Задачник Базовый курс EN

Задача

Слить соседние

динамика оптимизация

Текст лежит в n файлах подряд, и их надо склеить в один. Склеивать можно только два соседних файла; склейка стоит столько, сколько знаков в получившемся файле, и он встаёт на место двух. В каком порядке склеивать, чтобы общая цена была наименьшей?

Третий тест — 370 строф «Евгения Онегина», каждая отдельным файлом.

Вход

В первой строке n (1 ≤ n ≤ 1200). Во второй — размеры файлов a1, …, an (1 ≤ ai ≤ 10⁶).

Выход

Наименьшая общая цена. Если файл один, склеивать нечего — 0.

Примеры

Пример 1

Вход
4
4 1 2 3
Выход
19

Пример 2

Вход
1
7
Выход
0

Ограничения

Время · Python
5000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
8 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Последняя склейка соединяет два файла, каждый из которых склеен из отрезка исходных. Значит, это динамика на отрезках: cost[i][j] = minm (cost[i][m] + cost[m + 1][j]) + сумма отрезка. Сколько это при n = 1200?

2Подсказка 2

Около n³/6 — трёхсот миллионов шагов. Цена отрезка — его сумма; для неё неравенство четырёхугольника выполняется с равенством, и при расширении отрезка она не убывает. Что тогда можно сказать о лучшей точке последней склейки?

3Идея

Окно Кнута: при таких условиях лучшая точка m для [i, j] лежит между лучшими для [i, j − 1] и [i + 1, j] (Кнут, Яо). Перебираем m только в этом окне — и вся таблица стоит O(n²).

4Разбор

Идём по длинам отрезков от 2 до n. Для отрезка [i, j] окно — от best[i][j − 1] до best[i + 1][j], урезанное до j − 1; лучшую точку запоминаем в best[i][j]. У отрезков длины 1 лучшая «точка» — сам i. Таблицы — n² чисел: 1,4 миллиона, по 8 байт для цены и 4 для точки.

4+Решение
5Сложность

O(n²): окна отрезков одной длины вместе покрывают не больше 2n точек. Цена не больше n · Σa ≈ 1,4 · 10¹² — 64 бита.

6Типичные ошибки
  • Перебор всех m. Это wrong.py: на 370 строфах «Онегина» он ещё успевает, на 1200 файлах — нет.
  • Жадность Хаффмана. Склеивать два самых маленьких можно, только если они соседи. Хаффман с произвольными парами здесь неприменим, а «склеивать самую лёгкую соседнюю пару» не оптимально: для 8, 8, 5, 7, 4 она даёт 77, а лучший порядок — 75.
  • Окно без урезания. best[i + 1][j] может равняться j, а точка склейки для [i, j] должна быть меньше j.
  • Порядок таблицы. Нужны готовые ответы для отрезков на единицу короче — идите по длинам, а не по левому концу.

Алгоритмы задачи

DP Приём Оптимизации Кнута и «разделяй и властвуй» 45 тысяч городов на карте по классам населения: 3,5 млн вычислений вместо пяти миллиардов — потому что лучший разрез монотонен. O(k · n log n) 2 задачи DP Приём Динамика на отрезках Состояние — отрезок [i, j], переход — где его разрезать: дерево поиска, порядок умножения матриц, распил. O(n³) 2 задачи
Каталог алгоритмов