How to solve the cucumber problem?

Question

IT education

Cucumber problem.
A field of nxm square cells is given, each of which can contain plantings of cucumbers.
It is necessary to build greenhouses covering cucumbers. Greenhouses can only be rectangular, only with sides parallel to the sides of the field. The cost of building one greenhouse consists of two components - a known constant and a value proportional to the area of ​​the greenhouse. A greenhouse can cover only an integer number of cells. Find out which options for building greenhouses are the least expensive, provided that all cells with cucumbers are closed from the weather.
// In general, tell me in which direction to move.
What did I think?
We have the density coefficient of cucumbers, this is the number of cucumbers divided by the total cells. And so we choose such places for greenhouses that turn out to be maximum in size AND the density coefficient in them is GREATER or EQUAL to the total coefficient - this will be optimal, BUT when passing from the beginning and from the end, we get DIFFERENT results and it is not clear where to start the search, and in generally difficult. Who can help...

Answer 1

If one of the sizes is not very large, for example, no more than 15, dynamic programming will work.
We go across the field from the narrow side, moving the line each time by one cell. For a specific configuration of hotbeds, at every moment the line is divided into segments, each of which can either belong to its own hotbed, or be empty (not covered with hotbeds). In this case, segments with greenhouses can touch each other, but empty segments cannot, they merge into one. In addition, we remember the accumulated penalty for created (including closed) greenhouses and their area.
At each step, we can:
- first close some greenhouses (the corresponding segments will become empty)
- extend the remaining greenhouses by another cell (the number of cells of these greenhouses is added to the penalty)
- open new greenhouses in empty places (the cost of opening these greenhouses and the number of cells in them is added to the penalty).
In this case, all cells with cucumbers should be closed. It makes no sense to open new greenhouses in which there is not a single cucumber yet. All other options must be considered.
We start with one empty segment. At each step, we process all available configurations and build their extensions. From the equivalent new configurations (in which the segment maps are the same), we choose the one with the smaller penalty.
Everything. It remains to figure out how to cheaply store the paths traveled in order to restore the result later.

Answer 2

Let's call a normalized greenhouse in which there are no "empty" boundaries, i.e. there is at least one cucumber on the top, bottom, right and left borders.
Let's start with one greenhouse covering the entire field. We normalize it, we consider the cost.
We consider all options for splitting one straight line (we go through all internal verticals, then horizontals). For each partition, we normalize the resulting greenhouses and calculate the cost. Then we take the partition with the smallest cost. If this value is greater than or equal to the original, keep the original greenhouse, END. Otherwise, we use two new greenhouses and run this algorithm recursively for each of them.
EDIT: Doesn't work for all kinds of fields. Counterexample in the comments.

Answer 3

The cost of greenhouse #1 is p1 = x*S1 + c
The cost of all greenhouses (with numbers from 1 to n) p = x*S1+c+ ... + x*Sn+c
Parentheses p = x*(S1 + ... Sn) + c*n
By the condition of the problem, the sum of the areas of all greenhouses is equal to the area of ​​the field. Therefore, the cost of construction depends on the number of greenhouses n. The fewer greenhouses, the cheaper.