用一个一维数组记录‘矩形到当前这一排的高度’，一排一排地读
一排一排地处理；在读入地时候，如果是‘F’，h[i]++, 如果是‘R’，h[i]=0
然后对当前地 h[maxn] 数组求 最大的矩形面积（应该能理解吧）
用动态规划可以达到 平均情况下的线性算法

当m排扫描完的时候，结果就出来了

这样的方法，平均情况下是 n^2 的

（还要多谢 xiaomi 的提醒～～～ ）

• 线性算法 是怎么来的？ 我只能想到RMQ.. (221) yiyiyi4321 2007-06-06 14:48:12
• 谢谢啦～～～ (0) alpc55 2008-05-23 20:50:42