Ровный правый край
Абзац из n слов надо набрать в колонку шириной W знаков, не меняя порядка слов. Слово i занимает ai знаков, между соседними словами в строке — один пробел, длина строки — сумма длин её слов плюс число пробелов. Строка не может быть длиннее W; каждое слово по отдельности помещается.
Недобор строки — сколько знаков ей не хватает до W. Хочется, чтобы правый край был ровным: найдите наименьшую сумму квадратов недобора по всем строкам, кроме последней. Последняя строка может быть любой длины и в сумму не входит.
Вход
В первой строке — n и W (1 ≤ n ≤ 5·104, 1 ≤ W ≤ 100). Во второй — n длин слов a1, …, an (1 ≤ ai ≤ W).
Выход
Одно число — наименьшая сумма квадратов недобора.
Первый пример — фраза «Сложение двух чисел — треть наносекунды.» в колонке из 19 знаков. Жадный перенос кладёт в первую строку три слова и оставляет недобор 0 и 12 — сумма 144. Лучше «Сложение двух / чисел — треть / наносекунды.» с недобором 6 и 6 — сумма 72. Во втором примере — вводный абзац статьи о динамическом программировании в колонке из 35 знаков.
Примеры
Пример 1
6 19 8 4 5 1 5 12
72
Пример 2
90 35 2 7 8 2 4 8 3 9 2 7 7 4 9 2 7 2 7 6 9 11 5 1 5 3 11 7 6 1 5 6 5 1 22 10 5 8 2 9 1 7 8 2 10 1 9 6 1 5 4 7 3 5 2 12 1 2 11 2 6 9 3 9 8 3 7 11 1 7 9 5 2 4 1 5 7 1 9 1 5 7 5 1 5 3 6 1 13 3 6 8
474
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Где кончается предпоследняя строка? Если это известно, что можно сказать о том, как разбиты все слова до неё?
2Идея
Пусть cost[j] — наименьшая сумма для первых j слов, если строка обрывается после слова j. Последняя из этих строк начинается с какого-то слова i + 1, и всё до неё разбито лучшим образом: иначе, заменив начало на лучшее, мы уменьшили бы и сумму. Поэтому cost[j] = min по i из cost[i] + (W − длина слов i + 1..j)2, по всем i, при которых строка помещается. Для j = n квадрат не прибавляется — это последняя строка. Это кратчайший путь по графу мест разрыва из статьи.
3Разбор
Для каждого j перебираем начало строки i справа налево и наращиваем длину строки; как только она превысила W, дальше идти незачем — строка только длиннее. В строку помещается не больше (W + 1)/2 слов, поэтому на каждое j уходит не больше 51 шага. Ответ — cost[n].
Сумма не превышает n·W2 = 5·108, в Go хватит обычного int.
3+Решение
4Сложность
O(n·W) времени и O(n) памяти.
5Типичные ошибки
- Жадный перенос. Он даёт наименьшее число строк, но не ровный край: первый пример — 144 вместо 72.
- Считать последнюю строку. Тогда алгоритм начнёт растягивать её до края за счёт остальных строк.
- Не обрывать цикл. Перебор всех i от 0 до j − 1 даёт тот же ответ, но за O(n2) — на 50 000 словах это больше миллиарда шагов.