#35451: M^2 * N 解法, 將問題拆成每個連續列的組合, 再將問題降成1維並從中找最長連續子序列
quency89513@gmail.com
(QC Lin)
學校
:
不指定學校
編號 : 205592
來源 : [140.113.195.205]
最後登入時間 ：
2023-03-26 17:42:57
/* Solution
First, go through every possible possible combination of contiguous rows.
Consider the example:
row A A1 A2 A3 A4 A5
row B B1 B2 B3 B4 B5
row C C1 C2 C3 C4 C5
row D D1 D2 D3 D4 D5
In this example, (every possible combination of contiguous rows)
would be row A, AB, ABC, ABCD, B, BC, BCD, C, CD, D.
We take each combination as a sub problem and find the maximal rectangle of 0s of each sub problem.
In each sub problem, we only need to find the rectangle with HEIGHT = (height of the sub problem),
since heights smaller than HEIGHT are handled in other sub problem.
The goal now is to find the area of the rectangle with fixed height=HEIGHT and maximal width.
In each sub problem, we sum in vertical direction (sum by column),
taking 1s as 0s and 0s as 1s since we take the land without a tree.
So we will have an array col_sum[0..N], where N = # of columns of original problem = # of columns of sub problem
For col_sum[i]=HEIGHT, that means colmun i in the sub prolem is all 0s.
Just find the sub sequence in col_sum[] that has max number of contiguous (HEIGHT).
The lenght of the sub sequence will be WIDTH.
The answer to this sub problem will be HEIGHT * WIDTH.
Solve every sub problem,
and the max among answers of these sub problem is the answer to the original problem.
Similar to onlinejudge/108_Maximum_Sum
*/
ZeroJudge Forum