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

求最大子矩阵的两种思路 长沙市雅礼中学 贺一骏 编者：求最大子矩阵问题是很常见的一类问题，具有很强的代表性，通过这个问题，可以派生出更加复杂的问题，也可以学到很多常用的问题处理手段。 问题描述 一个被分为 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 4 1 2 3 4 5 0 6 3 10 3 4 0 Sample 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 Area[I,j]:=area[i-1,j]+area[i,j-1]-area[i-1,j-1]+mooncake[i,j]; 其边界条件为area[0,i]=0,area[i,0]=0 Mooncake[i,j]表示(i,j)这个点的上月饼数目，如果(i,j)这个点被破坏，则设mooncake[i,j]=那么有area[i,j]0。 显然，对于给定的两个点A（x1,y1）、B(x2,y2)，我们可以算术方法计算该矩形的和，如下图所示： 图1 预处理计算过程图 主程序如下： For x1:=1 to n do For x2:=x1 to n do For y1:=1 to m do For y2:=y1 to m do Begin Sum:=area[x2,y2]-area[x1-1,y2]-area[x2,y1-1]+area[x1-1,y1-1]; If sum0 then updateans(sum); End; 因此算法的时间复杂度为O(m2n2)。 从上述程序中可以看出，枚举点的坐标和预处理的过程有多次重复操作，也就是说在上述算法的运算中存在着很多冗余运算，如果我们能消除这些冗余运算，将能提高程序效率。下面请看算法二。 方法2 如何减少冗余呢？我们不妨这样的思考，上面的枚举实际将所有的矩形，不管有用无用全部枚举了出来。其实，对于大部分无用的矩形是可以不需要枚举就可以排除在最优解之外的，而有用的矩形指的是那些极大化矩形。 所谓极大化的矩形就是指那些不能再通过扩展边来再次增大面积的矩形。这样的矩形之所以无法再扩展是因为它们的四条边要么靠障碍物，要么靠着边界。例如下图中A的黄色部分就是一个极大化矩形，而B不是（它的右边界还可以向右延伸到边界），因此我们可以根据这一特点来找到所有的极大化矩形。 图2 极大化矩形 为了完成寻找极大化矩形的工作，我们先来看一个这样的子问题： 问题描述：给出若干个连在一起的高塔，已知每个塔的高度，询问对于每个高塔而言向左、右延伸的距离分别是多少（所谓延伸就是指向一个方向不断的寻找，直到找到一个高度低于本身的高塔或者边界为止，如下图）。 图3 塔的示意图及相关变量定义 说明：上图中p[i]为塔的坐标，h[i]为塔的高度，l[i]为塔尖向左延伸的最远坐标位置，r[i]为塔尖向右延伸的最远坐标位置 这里，我们只考虑向右的情况。向左操作类似。 我们从右向左扫描，当求r[i]时，r[i+1..n]已求出。首先，令r[i]=i，当h[i]=h[r[i]+1]时，就表示位置i向右最多可以延伸到位置r[r[i]+1]，更新r[i]，然后，继续比较h[i]与h[r[i]+1]的大小，不断的更新r[i]，直到h[i]h[r[i]+1]为止。 图4、5、6演示了k=4时的操作过程。 图4 步骤1，赋初值r[4]=4 图5 步骤2，