Click to watch
Click to watch
The meaning of the question is to ask you to find the maximum submatrix sum
is the two-dimensional expansion of the maximum subsection sum
When doing it, you still need some skills
The direct brute force search for this question will definitely be TLE (master difficulty, the person who asked the question can not make a simple brute force search)
We can convert the R, F matrix of the original image into a 01 matrix, and then traverse by row , Each time record the serial number of the largest column up to 1 found in the current row… Um, let’s give a picture.
< blockquote>
Then, when 1 is encountered, it is recorded as up[i][j] = up[i][j-1] Similar to the prefix sum, when 0 is encountered, it is reset to 0
< p>
When each line is traversed, if it encounters a smaller value than the previously recorded maximum value, the area is directly calculated (the length is the maximum value, and the width is the current serial number minus the Column serial number), each time you take max with the current answer, you can take similar operations if you encounter a value larger than the current maximum. Obviously these operations are monotonic, so it will be much simpler to use monotonic stack maintenance.
(STL Dafa is good)
Shenben all say it is a big water problem. . . . . . . . . .
The code is as follows:
//gtnd zcw#include while(!s.empty()) {int u = s.top(); s.pop(); ans = max(ans,(m-u+ 1) * h[i][u]);}} printf("%d
" ,ans*3); return ;}int main(){ rd(n);rd(m); work();return 0;}
THE END
By Peacefuldoge
http://blog.csdn.net/loi_peacefuldog/
Click to watch< Rainbow Cat and Blue Rabbit Seven Swordsman>
Click to watch
The meaning of the title is to ask you to be the biggest child Matrix sum
is the two-dimensional expansion of the largest sub-segment sum
When doing it, some skills are still needed
This problem will definitely be TLE (master difficulty, out of It is impossible for the questioner to make a simple brute search)
We can convert the R, F matrix of the original image into a 01 matrix, and then traverse according to the row, each time the current row is currently searched and the largest upward is 1 The serial number of a column… Uh, give me a picture
Then, 1 record is up[i][ j] = up[i][j-1] is similar to prefix sum, reset to 0 when encountering 0
When each line is traversed, if it encounters a smaller value than the previously recorded maximum value, the area is directly calculated (the length is the maximum value, and the width is the current serial number minus the serial number of the column). The previous answer is max. If you encounter something larger than the current one, you can also take similar operations. Obviously these operations are monotonic, so it will be much simpler to use monotonic stack maintenance.
(STL Dafa is good)
Shenben all say it is a big water problem. . . . . . . . . .
The code is as follows:
//gtnd zcw#include while (!s.empty()) {< span class="hljs-keyword">int u = s.top(); s.pop(); ans = max(ans,(m-u+1< /span>) * h[i][u]);}} printf("%d
",ans*3); return; }int main(){ rd(n);rd(m); work();return < span class="hljs-number">0;}
THE END
By Peacefuldoge
http://blog.csdn.net/loi_peacefuldog/