Рассмотрим квадрат N x N целых чисел, который вы можете разрезать по вертикали или по горизонтали K раз. Вы хотите попытаться минимизировать наибольшую сумму в каждом из полученных ящиков после разрезания. Распечатайте эту самую большую сумму.
Бонус: распечатайте расположение разрезов, дающее наименьшую сумму.
Подсказка: используйте манипуляции с битами
Например, учитывая, что вам разрешено 2 разреза и сетка
1 0 1 4
1 0 1 0
1 2 1 4
Разрезав его так:
1 0 1 | 4
1 0 1 | 0
---------
1 2 1 | 4
Вы можете минимизировать максимальную сумму в любом из четырех квадрантов, и вы напечатаете 4.
Первое, что я отмечу, это то, что, учитывая максимальное количество сокращений K, в ваших интересах использовать все K сокращений.
Одна вещь, о которой я подумал, это бинарный поиск позиций разреза, чтобы минимизировать сумму в каждой левой/правой половине, а затем бинарный поиск верха/низа, но как бы вы расширили это до более чем 2 разрезов?
Намек на манипулирование битами также заставляет меня думать, что некоторое динамическое программирование с использованием битовых масок является предполагаемым решением.
Есть идеи?
