求最大子矩阵的两种思路.doc

求最大子矩阵的两种思路长沙市雅礼中学 贺一骏编者：求最大子矩阵问题是很常见的一类问题，具有很强的代表性，通过这个问题，可以派生出更加复杂的问题，也可以学到很多常用的问题处理手段。问题描述 一个被分为 n*m个格子的月饼盒，第 i 行第 j 列位置的格子里面有 a i , j 个月饼。本来CCC老师打算送这盒月饼给某人的，但是就在要送出月饼盒的前一天晚上，一只极其可恶的老鼠夜袭月饼盒，有部分格子被洗劫并且穿了洞。CCC老师必须尽快从这个月饼盒里面切割出一个矩形月饼盒，新的月饼盒不能有洞，并且CCC老师希望保留在新月饼盒内的月饼的总数尽量多。任务：请帮CCC老师设计一个程序，计算一下新月饼盒最多能够保留多少月饼。 输入文件的第一行有两个整数 n、m。第 i + 1 行的第 j 个数表示 a i , j ，如果这个数为 0 ，则表示这个位置的格子被洗劫过。其中：1 n，m 300，0 a i , j 255输出 在文件中写入最大月饼数。 样例Sample Input 3 41 2 3 45 0 6 310 3 4 0Sample Output 17分析该问题实际上是求在给定平面区域中找出一个最大的子矩形，要求该矩形不能包含某些限定的格子。方法一：我们初次见到这个问题，可能最直接的想法就是枚举。即枚举每个矩阵的左上角坐标（x1,y1）和右下角坐标(x2,y2)，然后统计这个矩阵是否满足题设条件。我们可以先预处理从左上角（1,1）出发到任意一点（i,j）的月饼数目area(i,j)，预处理的时间复杂度为O(mn),程序如下：For i:=1 to n do For j:=1 to m do AreaI,j:=areai-1,j+areai,j-1-areai-1,j-1+mooncakei,j;其边界条件为area0,i=0,areai,0=0Mooncakei,j表示(i,j)这个点的上月饼数目，如果(i,j)这个点被破坏，则设mooncakei,j=-30000000，那么有areai,j0 then updateans(sum); End;因此算法的时间复杂度为O(m2n2)。从上述程序中可以看出，枚举点的坐标和预处理的过程有多次重复操作，也就是说在上述算法的运算中存在着很多冗余运算，如果我们能消除这些冗余运算，将能提高程序效率。下面请看算法二。方法2如何减少冗余呢？我们不妨这样的思考，上面的枚举实际将所有的矩形，不管有用无用全部枚举了出来。其实，对于大部分无用的矩形是可以不需要枚举就可以排除在最优解之外的，而有用的矩形指的是那些极大化矩形。所谓极大化的矩形就是指那些不能再通过扩展边来再次增大面积的矩形。这样的矩形之所以无法再扩展是因为它们的四条边要么靠障碍物，要么靠着边界。例如下图中A的黄色部分就是一个极大化矩形，而B不是（它的右边界还可以向右延伸到边界），因此我们可以根据这一特点来找到所有的极大化矩形。图2 极大化矩形为了完成寻找极大化矩形的工作，我们先来看一个这样的子问题：问题描述：给出若干个连在一起的高塔，已知每个塔的高度，询问对于每个高塔而言向左、右延伸的距离分别是多少（所谓延伸就是指向一个方向不断的寻找，直到找到一个高度低于本身的高塔或者边界为止，如下图）。图3 塔的示意图及相关变量定义说明：上图中pi为塔的坐标，hi为塔的高度，li为塔尖向左延伸的最远坐标位置，ri为塔尖向右延伸的最远坐标位置这里，我们只考虑向右的情况。向左操作类似。我们从右向左扫描，当求ri时，ri+1.n已求出。首先，令ri=i，当hihri+1为止。图4、5、6演示了k=4时的操作过程。图4 步骤1，赋初值r4=4图5 步骤2，向右更新 r4=6图6 步骤3，向右更新 r4=9代码如下（向右延伸）：For i:=m downto 1 do Begin Ri:=I; While (rim)and(hi=hri+1) do ri:=rri+1; End;这样做完后ri里保存的就是每个位置向右扩展的最远距离了。因为每个位置最多被后面的位置合并一次，因此这个算法的时间复杂度为O(N)。回到原问题，下面来看看如何求极大化矩形。枚举原矩形的每一行，首先更新hi，这里的hi表示第i列从当前行往上数有多少格连续没有被损坏的格子（直到上边界为止）。显然，这里的hi和子问题中的hi相同。因此利用处理子问题的方法，求出li和ri，接着根据li和ri，对于当前行的每一个位置k，有长为rk-lk+1，宽为hk的符合题设要求的矩形，并且这个矩形就是极大化矩形，算法一中的预处理方法，可求出这个矩形中月饼数目。下面来分析一下时间复杂度：枚举每一行，时间复杂度为O(N)，更新hi 为O(M)，求li和ri为O(M)，枚举k，为O(M)，因此，总时间复杂度为O(NM)，是一个非常优秀的算法。思考与总结：对于这类问题往往一开始就会有一些简单的想法，虽然实际效果并不是非常好，但是其思考方法总是可以借鉴的。像本题中就由简单的