对最大全零子矩阵的研究

JSOI2012江苏省队论文对最大全0子矩阵问题的研究常州市第一中学包奇2012/5/[e-mail]1对最大全0子矩阵问题的研究【摘要】最大全0子矩阵问题是信息奥赛中的一个经典问题。本文主要介绍最大全0子矩阵问题的多种求解方法。【关键字】枚举单调队列构造目录正文...............................................................................................................................................2问题描述...................................................................................................................................2算法分析...................................................................................................................................2算法1................................................................................................................................2算法2................................................................................................................................2算法3................................................................................................................................2算法4................................................................................................................................2算法5................................................................................................................................2算法6................................................................................................................................3算法总结...........................................................................................................................4总结...............................................................................................................................................4附录...............................................................................................................................................42问题描述给定一个n*m的0、1矩阵，求一个最大的全0子矩阵。算法分析对于这个问题，首先想到的就是枚举算法。1、先枚举左上角顶点和右下角顶点，再依次检验每个矩阵是否合法，这个算法的时间复杂度为O(n^6)（参考程序见附件1）。2、检验一个矩阵是否合法可以用部分和在O(1)的时间内完成，通过这个优化可以将时间复杂度降到O(n^4)（参考程序见附件2）。上述枚举算法的时间复杂度太高不能解决问题。一个问题的解法，往往可以由一个简单问题的解法推广而来，这个问题也不例外，我们不妨另辟蹊径将问题简化。我们可以先令n=1，那么这个问题就可以在O(n)时间内扫描出解。将这个算法推广到二维，我们就得出了如下算法：3、枚举上下边界，将二维矩阵压缩成一维而后扫描出解（参考程序见附件7），时间复杂度为O(n^3)。回到最朴素的枚举算法进行思考，我们发现朴素算法之所以时间复杂度高是因为它对决定一个矩形的所有量进行枚举。我们可不可以枚举一部分再计算一部分呢？答案显然是肯定的。对于一个子矩阵而言，只要确定了底边，高度就可以计算出来，它的高度就是底边上各个点向上延伸的高度的最小值，而对于一个点向上延伸的高度可以用一个数组H动态的维护：H[i][j]=H[i-1][j]+1(A[i][j]==0&&i!=1)=0(Else)基于这个思想，我们就得出了如下算法：4、枚举子矩阵的底边（右下角顶点、高度），逐个求解更新最优值，时间复杂度：O(n^3)（参考程序见附件3）。仔细整理和观察算法4中枚举到的矩形，不难发现，其中很多矩形明显可以向左右拓展形成更优的解。算法4中，我们枚举了很多这样的矩形。其实，我们完全可以避免枚举这些矩形，这可以用单调队列来实现。基于这个思想，我们就得出了如下算法：5、每个元素依次进队，并在该元素退队的时候将以该元素的值为高度、以该元素的插入位置与扫描列之间的线段为宽度构成的子矩阵更新答案，在这个算法中每个元素进队一次出队一次，这样就把时间复杂度降到了O(n^2)（参考程序见附件4）。具体操作如下图所示：3上述算法都是基于枚举的思想。那么可不可以构造呢？一个点要想构造出一个矩形就要向四周延伸。我们可以先将点向上延伸，再将延伸出的部分向左右延伸。这样就可以构造出一个矩形。下面就是要证明最优解可以通过这种方法构造出来。假定一个矩形是一个最优解，那么这个矩形就不能再向外拓展，那么在紧靠这个矩形的四边的点上必然存在一些黑点（即a[i][j]==1），我们称这些点为限制点。那么由在矩形底边上并且上方有限制点的那些点经上述方法拓展后一定能拓展出这个最优矩形。在这个方法中，我们要维护一个点向左延伸的最大距离L与一个点向右延伸的最大距离R。维护方法如下：L[i][j]=min(L[i-1][j],tl)R[i][j]=min(R[i-1][j],tr)（其中tl、tr是当列能向左、右方向延伸的距离）于是我们就得出了如下算法：6、依次扫描每一个点，对于每一个点按照上述方法维护L、R、H三个量，用每个点的(R+L-1)*H更新答案即可（参考程序见附件5）。4现在，我们比较一下以上六种算法。算法时间复杂度空间复杂度[最低]编程复杂度小结1O(n^6)O(n^2)★时间复杂度过高，不能解决问题，但编程复杂度低，建议在缺乏时间的情况下使用2O(n^4)O(n^2)★3O(n^3)O(n^2)★用解决一维问题的算法推广而来。对解决其它类似问题有很高的借鉴价值。4O(n^3)O(n)★挖掘了问题的一些性质，用枚举底边计算高度代替了枚举左上右下顶点从而降低了时间复杂度5O(n^2)O(n)★★★巧妙利用单调队列避免了无效状态的枚举，但该方法需要用到一个高级数据结构——单调队列，编程复杂度和思维复杂度很高6O(n^2)O(n)★充分挖掘了问题的性质，用构造的方法构造出最优解，时间复杂度达到理论下界，不失为一种绝佳的方法问题拓展给定一个n*m*p的0、1立方体，求最大全0子立方体。通过枚举高度和起点将三维立方体压缩成二维矩阵再通过上述方法求解，时间复杂度：O(n^4)（参考程序见附件6）。【总结】在面对一道较为简单的题目时，许多选手常常在想到一种AC算法后就不去深入思考。殊不知，一题多解不仅是对题目本质的深入挖掘和探讨，也是对自己分析与思考能力的极大锻炼。求解一个问题不能浅尝辄止，而应该从各个角度进行思考，尝试一题多解，从而实现对问题的彻底解决。【附录】附件1：2D[1].cpp附件2：2D[2].cpp附件3：2D[3].cpp附件4：2D[4].cpp附件5：2D[5].cpp附件6：3D.cpp附件7：2D[6].cpp