house_count домов, цвета пронумерованы от 1 до color_count. Некоторые дома покрасили прошлым летом — их не перекрашивают. colors[i] — цвет дома i, или 0, если он ещё не покрашен. price[i][c - 1] — стоимость покраски дома i в цвет c.
Цветовой квартал — это максимальный непрерывный участок домов одного цвета. Например, у улицы [1, 2, 2, 3, 3, 2, 1, 1] пять кварталов: [1], [2, 2], [3, 3], [2], [1, 1].
Покрасьте все непокрашенные дома так, чтобы кварталов получилось ровно blocks, и верните наименьшую стоимость. Если это невозможно, верните -1.colors=[0, 0, 0], price=[[1, 5], [4, 2], [3, 3]], house_count=3, color_count=2, blocks=1 → 8
Один квартал — значит, все дома одного цвета. Всё в цвет 1 стоит 1 + 4 + 3 = 8, всё в цвет 2 — 10. Ответ 8.
colors=[0, 2, 0], price=[[1, 5], [4, 2], [3, 3]], house_count=3, color_count=2, blocks=2 → 4
Дом 1 уже покрашен в цвет 2 и не перекрашивается. Красим дом 0 в цвет 1 (1), дом 2 в цвет 2 (3): получаем [1, 2, 2] — два квартала за 4.
colors=[1, 2, 1], price=[[1, 1], [1, 1], [1, 1]], house_count=3, color_count=2, blocks=2 → -1
Все дома уже покрашены, и кварталов три, а не два. Ответ -1.
house_count ≤ 100color_count ≤ 20colors) = len(price) = house_count, len(price[i]) = color_countblocks ≤ house_countcolors[i] ≤ color_countprice[i][j] ≤ 10⁴colors=[0, 0, 0], price=[[1, 5], [4, 2], [3, 3]], house_count=3, color_count=2, blocks=1
8
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 69 тестов на сервере, включая скрытые.