BZOJ 2975 [Poi2002] 最大的园地


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

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


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

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

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2975 [Poi2002] 最大的园地


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,