还剩3页未读,继续阅读
文本内容:
求最大子矩阵的两种思路长沙市雅礼中学贺一骏编者求最大子矩阵问题是很常见的一类问题,具有很强的代表性,通过这个问题,可以派生出更加复杂的问题,也可以学到很多常用的问题处理手段问题描述一个被分为n*m个格子的月饼盒,第i行第j列位置的格子里面有a[ij]个月饼本来CCC老师打算送这盒月饼给某人的,但是就在要送出月饼盒的前一天晚上,一只极其可恶的老鼠夜袭月饼盒,有部分格子被洗劫并且穿了洞CCC老师必须尽快从这个月饼盒里面切割出一个矩形月饼盒,新的月饼盒不能有洞,并且CCC老师希望保留在新月饼盒内的月饼的总数尽量多任务请帮CCC老师设计一个程序,计算一下新月饼盒最多能够保留多少月饼输入文件的第一行有两个整数n、m第i+1行的第j个数表示a[ij],如果这个数为0,则表示这个位置的格子被洗劫过其中1≤n,m≤300,0≤a[ij]≤255输出在文件中写入最大月饼数样例SampleInput341234506310340SampleOutput17分析该问题实际上是求在给定平面区域中找出一个最大的子矩形,要求该矩形不能包含某些限定的格子方法一我们初次见到这个问题,可能最直接的想法就是枚举即枚举每个矩阵的左上角坐标(x1y1)和右下角坐标x2y2,然后统计这个矩阵是否满足题设条件我们可以先预处理从左上角
(11)出发到任意一点(ij)的月饼数目areaij,预处理的时间复杂度为Omn程序如下Fori:=1tondoForj:=1tomdoArea[Ij]:=area[i-1j]+area[ij-1]-area[i-1j-1]+mooncake[ij];其边界条件为area[0i]=0area[i0]=0Mooncake[ij]表示ij这个点的上月饼数目,如果ij这个点被破坏,则设mooncake[ij]=-30000000,那么有area[ij]0显然,对于给定的两个点A(x1y1)、Bx2y2,我们可以算术方法计算该矩形的和,如下图所示图1预处理计算过程图主程序如下Forx1:=1tondoForx2:=x1tondoFory1:=1tomdoFory2:=y1tomdoBeginSum:=area[x2y2]-area[x1-1y2]-area[x2y1-1]+area[x1-1y1-1];Ifsum0thenupdateanssum;End;因此算法的时间复杂度为Om2n2从上述程序中可以看出,枚举点的坐标和预处理的过程有多次重复操作,也就是说在上述算法的运算中存在着很多冗余运算,如果我们能消除这些冗余运算,将能提高程序效率下面请看算法二方法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,向右更新r
[4]=6图6步骤3,向右更新r
[4]=9代码如下(向右延伸)Fori:=mdownto1doBeginR[i]:=I;Whiler[i]mandh[i]=h[r[i]+1]dor[i]:=r[r[i]+1];End;这样做完后r[i]里保存的就是每个位置向右扩展的最远距离了因为每个位置最多被后面的位置合并一次,因此这个算法的时间复杂度为ON回到原问题,下面来看看如何求极大化矩形枚举原矩形的每一行,首先更新h[i],这里的h[i]表示第i列从当前行往上数有多少格连续没有被损坏的格子(直到上边界为止)显然,这里的h[i]和子问题中的h[i]相同因此利用处理子问题的方法,求出l[i]和r[i],接着根据l[i]和r[i],对于当前行的每一个位置k,有长为r[k]-l[k]+1,宽为h[k]的符合题设要求的矩形,并且这个矩形就是极大化矩形,算法一中的预处理方法,可求出这个矩形中月饼数目下面来分析一下时间复杂度枚举每一行,时间复杂度为ON,更新h[i]为OM,求l[i]和r[i]为OM,枚举k,为OM,因此,总时间复杂度为O__,是一个非常优秀的算法思考与总结对于这类问题往往一开始就会有一些简单的想法,虽然实际效果并不是非常好,但是其思考方法总是可以借鉴的像本题中就由简单的枚举出发,利用枚举矩形这个思考方式不断的优化,从而得到一个优秀的算法像这类问题的还有Zoj2069whiterectanglesZoj1985largestrectangleinahistogram等。