how to approach this problem?
Square painting problem
The Problem can be solved using the following approach:
To solve the problem for rectangle W×H (W≥H). Of course, we can cover all rectangle with itself for cost W. To get something smaller than W we have to leave at least one column uncovered — otherwise we pay at least sum of w over all rectangles which is at least W. This gives us an idea to use DP on rectangles to solve the problem: dp[x1][x2][y1][y2] is minimal cost to cover the rectangle [x1;x2)×[y1;y2). It is initialized by max(x2−x1,y2−y1), and we have to try not to cover every column/row. Of course, we have to check if it is all white from the beginning; to do that we will precalculate 2D prefix sums.
Apaar likes to paint his heart out. He made a famous painting software letspaint. The working screen of letspaint is square-shaped consisting of n rows and n columns of square cells. The rows are numbered from 1 to n, from top to bottom, and the columns are numbered from 1 to n, from left to right. The position of a cell at row r and column c is represented as (r,c). There are only two colors for the cells in letspaint — black and white.
There is a tool named eraser in letspaint. The eraser has an integer size k (1≤k≤n). To use the eraser, Apaar needs to click on a cell (i,j) where 1≤i,j≤n−k+1. When a cell (i,j) is clicked, all of the cells (i′,j′) where i≤i′≤i+k−1 and j≤j′≤j+k−1 become white. In other words, a square with side equal to k cells and top left corner at (i,j) is colored white.
A white line is a row or a column without any black cells.
Apaar has worked with letspaint for some time, so some of the cells (possibly zero or all) are currently black. He wants to know the maximum number of white lines after using the eraser exactly once. Help him find the answer to his question.
this is the problem.
yes i am talking about the same problem .Please go through the above algorithm .
Thanks!