poj 1964 City Game(单调栈,输入挂)

poj 1964

题意:n*m的maze,由’R’和‘F’组成,现在要求找到面积最大的矩形,使得矩形中所有格子都是’F’。

思路:单调栈…一开始神tm tle….复杂度没问题啊。。。

结果看到有人说这题由于数据量比较大。。。scanf会超时。。。所以要用输入挂。。。。。getchar什么的。。。

poj竟然也卡读入。。。人性呢。。。。

改了输出以后再交wa了。

发现想错了,我是写了从(i,j)到两个方向能到的最大距离。。但是这样写有些点上的情况是没有考虑到的。。比如如果(i+1,j+1)上的点是’R’,实际上是不可以构成l*r的矩形的(l>=2&r>=2)。。。但是我这样做无法体现。

改了下,变成:

仍然对于每行做一次单调栈,预处理出点(i,j)能往右的最远距离a[i][j]。

然后观察一下。。。如果我把每一列分别看成x轴,那a[i][j]不就是矩形的高度了吗。。。

那我要求的不又变成了最大矩形面积了吗。。。

于是接下来对于每一列,做上下两个方向的单调栈得到(i,j)上下能延伸到的最远距离。

(i,j)点所在的矩形面积就是 (r[i][j]-l[i][j]+1)*a[i][j];

再交,A了

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz