m1greatcool

Назовём нормализированым парник, в котором нет "пустых" границ, т.е. на верхней, нижней, правой и левой границах есть, как минимум, по одному огурцу.

Начнём с одной теплицы, охватывающей всё поле. Нормализируем её, считаем стоимость.

Рассматриваем все варианты разбиения одной прямой (проходимся по всем внутренним вертикалям, затем горизонталям). Для каждого разбиения нормализируем получившиеся теплицы, подсчитываем стоимость. Затем берём разбиение с наименьшей стоимостью. Если эта стоимость больше или равна оригинальной, оставляем оригинальную теплицу, КОНЕЦ. Иначе используем две новых теплицы и для каждой из них рекурсивно запускаем этот алгоритм.

EDIT: Не работает для всех видов полей. Контрпример в комментариях.

Если один из размеров не очень большой, например, не больше 15, сработает динамическое программирование.
Идём по полю с узкой стороны, двигая линию каждый раз на одну клетку. Для конкретной конфигурации парников у нас в каждый момент линия делится на отрезки, каждый из которых может либо принадлежать своему парнику, либо быть пустым (не покрытым парниками). При этом отрезки с парниками могут касаться друг друга, а пустые отрезки - нет, они сливаются в один. Кроме того, мы помним накопленный штраф для созданных (в том числе, закрытых) парников и их площади.
На каждом шагу мы можем:
- сначала закрыть некоторые парники (соответствующие отрезки станут пустыми)
- продлить остальные парники ещё на клетку (к штрафу добавляется число клеток этих парников)
- на пустых местах открыть новые парники (к штрафу добавляется стоимость открытия этих парников и число клеток в них).
При этом все клетки с огурцами должны оказаться закрытыми. Открывать новые парники, в которых пока нет ни одного огурца, смысла нет. Все остальные варианты должны быть рассмотрены.
Начинаем с одного пустого отрезка. На каждом шагу обрабатываем все имеющиеся конфигурации, строим их продолжения. Из эквивалентных новых конфигураций (в которых одинаковые карты отрезков) выбираем ту, у которой меньше штраф.
Всё. Осталось придумать, как дёшево хранить пройденные пути, чтобы потом восстановить результат.