Вечера чтения
Поэму читают вслух за k вечеров: строки по порядку, в каждый вечер — хотя бы одна строка, строку не разрывают. Вечер длиной L знаков утомляет на L²: длинный вечер тяжелее двух коротких. Разделите строки на k вечеров так, чтобы суммарная усталость была наименьшей, и выведите её.
В третьем и четвёртом тестах — 5273 строки «Евгения Онегина» (по числу знаков в строке), на 10 и на 30 вечеров.
Вход
В первой строке n и k (1 ≤ n ≤ 6000, 1 ≤ k ≤ min(n, 30)). Во второй — длины строк a1, …, an (1 ≤ ai ≤ 100).
Выход
Наименьшая сумма квадратов длин вечеров.
Примеры
Пример 1
5 2 3 1 4 1 5
100
Пример 2
9 3 10 10 10 1 1 1 10 10 10
1329
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Динамика по числу вечеров и прочитанным строкам: bestg[i] — наименьшая усталость, если первые i строк прочитаны за g вечеров. Перебор начала последнего вечера даёт k · n²/2 — полмиллиарда шагов. Что можно сказать о том, где начинается последний вечер, когда i растёт?
2Подсказка 2
Проверьте неравенство четырёхугольника для цены вечера w(j, i) = (pi − pj)², где p — префиксные суммы. Обозначьте суммы трёх кусков A, B, C и сравните (A + B)² + (B + C)² с (A + B + C)² + B².
3Идея
Разность правой и левой частей — 2AC ≥ 0, так что неравенство выполнено, и по теореме о монотонности лучшее начало последнего вечера не убывает с i. Каждый слой считаем «разделяй и властвуй»: середина — перебором в окне, половины — в суженных окнах.
4Разбор
Слой — стек отрезков (lo, hi, olo, ohi). Для середины mid перебираем j от olo до min(mid − 1, ohi), берём лучший arg; левой половине достаётся окно [olo, arg], правой — [arg, ohi]. Недостижимые состояния (вечеров больше, чем строк) — бесконечность; их нужно пропускать или складывать как бесконечность, а не как большое целое, иначе сумма переполнится.
4+Решение
5Сложность
O(k n log n): около двух миллионов вычислений цены при k = 30 и n = 6000. Ответ не больше (6 · 10⁵)² = 3,6 · 10¹¹ — помещается в 64 бита.
6Типичные ошибки
- Перебор начала вечера. Это
wrong.py: на «Онегине» за десять вечеров — уже 140 миллионов шагов, и в третьем тесте времени не хватает. - Жадность. «Читать, пока не наберётся среднее» во втором примере даёт вечера 30, 23 и 10 — 1529 вместо 1329: у строк разная длина, и граница, сдвинутая на строку, бывает выгоднее.
- Окно без ограничения j < i. Последний вечер не может быть пустым: правую границу окна урезают до mid − 1.
- Переполнение с бесконечностью. MaxInt64 + d² переполняется; состояния-бесконечности надо пропускать.