Everyone on the internet says to preprocess first, the key is how to preprocess. I don't know~~~
But finally, I understand some of it now.
-
First, calculate how many rectangles can be formed with each cell and the cell above it, and change 1 to 0.
-
Then, use a large enumeration of four directions: up, left, down, right. Calculate the maximum number of rectangles that can be formed with the cells within these four directions using the bottom right corner point.
So, as long as you add the points calculated in the first step to the current minimum value, don't calculate again when encountering 0.
- Add the number of u, l, d-1, r and u, l, d, r-1, of course, these have already been processed (and the points that need to be processed have also been processed (DP concept)), and because there may be overlapping parts, u, l, d-1, r-1 must be subtracted.