The teacher gives each student a 5 x 10 square paper, which can be colored on the paper. Later, she asked the students to do the following:
You can fill the space if they are not colored,
problem is to find the rectangle with the largest area of uncolored.
student will get a high score if after colored (or not colored) some spaces, the largest rectangle have the exact![alt text][1] area is S.
As a longtime person in the profession, the teacher knows sooner or later her student will ask how many different ways to color and how is the two different ways. The second question is not easy to answer: two different ways of coloring, if you stack two sheets of paper on top of each other (do not twist or flip the paper) have at least one pair of two overlapping spaces. Quantities need to be carefully calculated. Never give wrong answers to the children.
Requirements: For S and the color of the pre-filled paper. Determine the number of ways a high score is awarded.
input
4
1111111111
1111110011
0000010011
1111111111
1111111111
output
61
I would prefer it if you do the problems on your own, however I will provide a hint on this problem: Save a dynamic programming state on the current row and the 5 columns’ height, like in the histogram problem, then use it to figure out the maximum area in the current part and pass it up from below.
(Also your translation is questionable at a bunch of parts, I had to read the original task on my own)
em xin lỗi ạ, do mấy bài này còn thật sự khó với em. mà em ac bài này rồi cảm ơn anh.