BZOJ 2975 [Poi2002] 最大的园地

发布于 2017-06-27  103 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2975

题意:求一个 01 矩阵的最大全 0 子矩阵...


回过头刷水,才发现曾经学的时候并没有很清晰的理解... 只能现 YY 一发...

首先维护一个类似前缀和的\(b\) 数组,记录以每一行为基础能向上延伸的最长距离,对于每一行,\(O(n)\) 扫一次即可

具体怎么搞呢,考虑到在确定某一列向两侧延伸是不好处理的,我们保证递增后就只需要考虑右侧了,因为左侧一定不合法。

维护单调不递减栈即可,出栈累计宽度更新答案即可

 


一个非常弱的准退役OIER