Ctrl K

Задачи по дням

Сложная
Есть список задач с трудоёмкостями effort, и их нужно выполнить ровно за days дней. Задачи делаются строго по порядку: i-ю можно начать, только закончив все предыдущие. Каждый день нужно выполнить хотя бы одну задачу. Тяжесть дня — наибольшая трудоёмкость среди задач этого дня. Тяжесть плана — сумма тяжестей всех дней. Верните минимальную тяжесть плана или -1, если составить план нельзя.
Пример 1
effort=[3, 8, 2, 2, 5], days=2 → 11

Лучше всего в первый день сделать только задачу 3, а во второй — остальные: 3 + 8 = 11. Разбиение [3, 8] и [2, 2, 5] дало бы 8 + 5 = 13.

Пример 2
effort=[4, 4], days=3 → -1

Задач всего две, а дней три: в какой-то день делать будет нечего.

Пример 3
effort=[0, 7, 1, 6], days=4 → 14
Ограничения
  • 1 ≤ len(effort) ≤ 300
  • 0 ≤ effort[i] ≤ 1000
  • 1 ≤ days ≤ 10
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВода между стенами СложнаяСамый большой горящий блок СложнаяПрибыль за две сделки СложнаяВсе способы расставить пробелы СложнаяПереход через пещеру Сложная
загружаем Python…
Вход
effort=[3, 8, 2, 2, 5], days=2
Ожидается
11

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 96 тестов на сервере, включая скрытые.