Задача про парники

[Mamai123]

Здравствуйте. Помогите, пожалуйста, с алгоритмом решения

Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов.
Необходимо построить парники, закрывающие огурцы. Парники могут быть только прямоугольной формы, только со сторонами,
параллельными сторонам поля. Стоимость строительства одного парника складывается из двух составляющих - известной постоянной(С)
и величины, пропорциональной площади парника(Стоимость клетки, S). Парник может накрывать только целое количество ячеек. Выяснить какие варианты
строительства парников наименее затратны при условии, что закрытыми от не погоды оказываются все ячейки с огурцами.

Для начала я делил C на S без остатка. Получается число(K), которое соответствует максимальному количеству пустых ячеек в парнике. Соответственно, необходимо разбить все поле на наименьшее количество парников, в которых будет <=K пустых клеток.
Но каким образом это сделать?
Был вариант сначала разбить на вертикальные и горизонтальные теплицы с шириной в 1 клетку(т.к. в любом случае придется закрывать все огурцы), а потом объединять, но я так и не смог это реализовать до конца.

[Dimka-novitsek]

Я видно не понял. Просто строим парник на все поле сразу, в этом случае известной постоянной(С) будет только один раз, и парник выйдет дешевле. В чем еще прикол?

[Dimka-novitsek]

А, мы должны программно имитировать поле. Да.....