转 浅谈用极大化思想解决最大子矩形问题。浅谈用极大化思想解决最大子矩阵问题。

一、   问题

最好大子矩形问题:在一个加以的矩形网格中来一些障碍点,要寻找来网格中不含其他障碍点,且边界和坐标轴平行的卓绝大子矩形。

 

立刻是最近经常出现的题材,例如冬令营2002之《奶牛浴场》,就属最为大子矩形问题。

 

Winter Camp2002,奶牛浴场

题意简述:(原题见论文附件)

John要以矩形牛场中打一个大型浴场,但是这个大型浴场不克包含其他一个奶牛的产奶点,但产奶点可以发在浴室的鄂上。John的牛场和设计的浴池都是矩形,浴场要全在牛场之内,并且浴场的轮廓要跟牛场的概况平行或者重合。要求所求浴场的面积尽可能大。

参数约定:产奶点的个数S不超越5000,牛场的限N×M不超过30000×30000。

 

【摘要】

次、   定义及说明

第一肯定有概念。

 

1、定义有效子矩形呢内部未含其他阻碍点且边界与坐标轴平行的子矩形。如图所示,第一单凡是有效子矩形(尽管边界及有障碍点),第二独无是有效子矩形(因为中间含有障碍点)。

图片 1

 

2、粗大有效子矩形:一个有效子矩形,如果无存在包含它都较它非常的有效子矩形,就称此有效子矩形为庞大有效子矩形。(为了叙述方便,以下称极大子矩形

 

3、定义不过要命起效子矩形啊所来来效子矩形中最好深的一个(或多个)。以下简称也最大子矩形。

  

本文针对一类近期经常出现的有关最大(或最优)子矩形及相关变形问题,介绍了极大化思想在这类问题中的应用。分析了两个具有一定通用性的算法。并通过一些例题讲述了这些算法选择和使用时的一些技巧。

老三、   极大化思想

【定理1】在一个发障碍点的矩形中之无比大子矩形一定是一个极大子矩形。

证实:如果尽特别子矩形A不是一个极大子矩形,那么根据极大子矩形的概念,存在一个含有A且比A更要命的有效子矩形,这跟“A是极端大子矩形”矛盾,所以【定理1】成立。

 

图片 2

【关键字】 矩形,障碍点,极大子矩形

季、   从问题之特点入手,得到两种常用之算法

定理1虽可怜明朗,但可是好关键的。根据定理1,我们可以得这样一个解题思路:

经枚举所有的极大子矩形,就好找到最大子矩形。下面根据这思路来统筹算法。

约定:为了叙述方便,设尽矩形的高低为n×m,其中障碍点个数为s。

【正文】
一、 问题

算法1

算法的思路是经枚举所有的极大子矩形找有尽大子矩形。根据是思路好窥见,如果算法中生出同样不成枚举的子矩形不是有效子矩形、或者未是极大子矩形,那么可毫无疑问之算法做了“无用功”,这为便是内需优化的地方。怎样保证每次枚举的都是极大子矩形呢,我们事先打极大子矩形的特性入手。

图片 3

定理2】:一个极大子矩形的季长达边一定都非克向外扩张。更进一步地游说,一个有效子矩形是极大子矩形的充要条件是是子矩形的各国条边或覆盖了一个障碍点,要么与合矩形的边际重合。 

 

定理2的不利很明显,如果一个有效子矩形的有平等长长的边既没有盖一个障碍点,又不曾跟任何矩形的境界重合

,那么自然存在一个涵盖它的有效子矩形。根据定理2,我们可以抱一个枚举极大子矩形的算法。为了处理好,首先在障碍点的聚众中加上整个矩形四较量上的触及。每次枚举子矩形的内外左右界(枚举覆盖的障碍点),然后判断是否合法(内部是否生隐含障碍点)。这样的算法时间复杂度为O(S5),显然太强了。考虑到极大子矩形不能够包含障碍点,因此这样枚举4个边界显然会发生大量底无效子矩形。

考虑只枚举左右边际的景况。对于曾经确定的左右疆,可以拿所有处在这个界限外之触发仍从上到下排序,如图1蒙所显示,每一样封锁就象征一个有效子矩形。这样做时间复杂度为O(S3)。由于保险每次得到的矩形都是官方的,所以枚举量比前同种植算法小了成千上万。但需留意的凡,这样做枚举的子矩形虽然是官方的,然而莫自然是宏大

图片 4

的。所以这个算法还有优化的余地。通过对斯算法不足之处的优化,我们好得一个飞速之算法。

忆上面的算法,我们不难察觉,所枚举的矩形的上下边界都埋了障碍点或者跟整矩形的界限重合,问题不怕在左右疆及。只有那些左右界也掩盖了障碍点或者和周矩形的边界重合的有效子矩形才是咱得着眼之极大子矩形,所以前面的算法做了多“无用功”。怎么压缩“无用功”呢,这里介绍一种植算法(算法1),它好用在过剩此类题材上。

算法的思绪是这般的,先枚举极大子矩形的左边界,然后从左到右依次扫描每一个障碍点,并不断改中的光景边界,从而枚举出所有坐这个定位为左边界的极大子矩形。考虑而图2蒙受之老三独点,现在我们如果确定有坐1如泣如诉点吧不当边界的宏大矩形。先用1哀号点右侧边的触及本横坐标排序。然后按从左到右的逐条依次扫描1号点右侧边的接触,同时记录下时底有效的内外边界。

开时令当前底前后边界分别吗全方位矩形的内外边界。然后起扫描。第一破碰到2声泪俱下点,以2声泪俱下点当右边界,结合当下之前后边界,就获取一个极大子矩形(如图3)。同时,由于所求矩形不克包含2如泣如诉点,且2如泣如诉点当1号点的江湖,所以要改时之下边界,即以2声泪俱下点之纵坐标作为新的下界。第二次等碰到3号接触,这时坐3哀号点的横坐标作为右边界又得博得一个饱性1的矩形(如图4)。类似的,需要相应地改达边界。以此类推,如果是点是在目前触及(确定左边界的触及)上方,则改达边界;如果以下方,则改下界;如果处在图片 5于平行,则可暂停搜索(因为后面的矩形面积且是0了)。由于曾当障碍点集合中增

这样做是否用富有的极大子矩形都枚举过了吧?可以窥见,这样做只考虑到了错边界覆盖一个碰的矩形,因此我们还用枚举左边界及任何矩形的左边界重合的情景。这尚可分成两看似情况。一种植是荒唐边界和成套举行的左边界重合,而右手边界覆盖了一个障碍点的情况,对于这种状况,可以就此类似之计从右到左扫描每一个沾当右边界的情事。另一样种是横边际都与任何矩形的左右疆重合的景,对于当下仿佛状况咱得以于先期处理面临好:先拿所有点按纵坐标排序,然后可以获以邻两单点的纵坐标为上下边界,左右界及整矩形的横境界重合的矩形,显然这样的矩形也是极大子矩形,因此呢欲给枚举到。加了合矩形右上斗与右下角的少个点,所以不见面遗留漏右边界与所有矩形的下手重合的极大子矩形(如图5)。需要小心的是,如果扫描到的点不在时底左右边界外,那么就无欲针对是点进

行处理。

由此前两步,可以枚举出所有的极大子矩形。算法1的时光复杂度是O(S2)。这样,可以缓解大部分极度大子矩形和血脉相通题材了。

图片 6

 

尽管如此上述之算法(算法1)看起是较快速之,但也发出采取的局限性。可以发现,这个算法的复杂度只跟障碍点的只数s有关。但于一些问题,s最酷起或达到n×m,当s较充分时,这个算法就不一定能满足时间达之求了。能否设计出一致种植据让n和m的算法也?这样于算法1不克奏效的时节咱们还有别的选择。我们重又打极度中心的题目开研究。

 

 

最好大子矩形问题:在一个加以的矩形网格中生一些障碍点,要物色来网格内不含有其他障碍点,且边界与坐标轴平行的顶大子矩形。

算法2

     
首先,根据定理1:最充分生效子矩形一定是一个极大子矩形。不过和前同种植算法不同之是,我们不再要求每一样不善枚举的自然是极大子矩形而只要求具备的极大子矩形都吃枚举到。看起这种算法可能比较前同一种植不同,其实不然,因为前面一样种算法并无是两全的:虽然每次考察之还是极大子矩形,但她还是开了点儿之“无用功”。可以窥见,当障碍点很密集的时刻,前一模一样种算法会做大量没因此底可比工作。要缓解此题材,我们得跳出前面的思绪,重新考虑一个新的算法。注意到极大子矩形的个数不见面超越矩形内单位方格的个数,因此我们发或找有一致栽时光复杂度是O(N×M)的算法。

 

 定义:

实惠竖线:除了个别个端点外,不挂任何障碍点的竖直线段。

图片 7

悬线:上端点覆盖了一个障碍点或达到任何矩形上捧的行之有效竖线。如图所示的老三单有效竖线都是悬线。

 

     
对于任何一个极大子矩形,它的直达边界及或者生一个障碍点,要么和全体矩形的达成边界重合。那么只要管一个极大子矩形按x坐标不同切割成多单(实际上是众多单)与y轴垂直的线条,则中肯定在同样长长的悬线。而且同样长长的悬线通过尽可能地于左右移动恰好能获一个子矩形(未必是极大子矩形,但一味可能于下扩展)。通过上述之解析,我们好获得一个着重之定律。

 

定理3】:如果拿一个悬线向左右个别个趋势尽可能挪动所得到的有效子矩形称为这个悬线所对应之子矩形,那么富有悬线所对应的有效子矩形的聚合一定带有了有着极大子矩形的会师。

 

定理3遭到之“尽可能”移动指的凡移动到一个障碍点或者矩形边界的位置。

根据【定理3】可以窥见,通过枚举所有的悬线,就好枚举出所有的极大子矩形。由于每个悬线都同它底部的十分点一一对应,所以悬线的个数=(n-1)×m(以矩形中除了顶部的接触以外的每个点呢底色,都足以取得一个悬线,且没有遗漏)。如果能够就对每个悬线的操作时间还也O(1),那么万事算法的复杂度就是O(NM)。这样,我们来看了化解问题的期。

     
现在的题材是,怎样当O(1)的日内形成对每个悬线的操作。我们解,每个极大子矩形都好透过一个悬线左右动得到。所以,对于每个确定了底的悬线,我们用了解关于于它们的老三个量:顶部、左右极多克走到之岗位。对于底部也(i,j)的悬线,设它的高为hight[i,j],左右极其多会活动至之职为left[i,j],right[i,j]。为了充分利用以前取的信,我们以立刻三单函数用递推的形式让闹。

 

  对于坐点(i,j)为根的悬线:

比方点(i-1,j)为障碍点,那么,显然以(i,j)为的的悬线高度为1,而且左右全都好倒至所有矩形的横界,即

 

 height[i,j]=l

left[i,j]=0

right[i,j]=m

苟接触(i-1,j)不是障碍点,那么,以(i,j)为之之悬线就等于为(i-1,j)为底之悬线+点(i,j)到点(i-1,j)的线。因此,height[i,j]=height[i-1,j]+1。比较麻烦的凡反正界,先考虑left[i,j]。如下图所示,(i,j)对应之悬线左右克移动的职务要在(i-1,j)的根底及扭转。

即left[i,j]=max( left[i-1,j] , (i-1,j)左边第一个障碍点位置 ) 如图

   图片 8

 right[i,j]的求法类似。综合起来,可以取得及时三独参数的递给推式:

 

height[i,j]=height[i-1,j]+1

left[i,j]=max( left[i-1,j] ,
(i-1,j)左边第一只障碍点位置,边界0也是障碍点 )

right[i,j]=min( right[i-1,j] ,
(i-1,j)右边第一个障碍点位置,边界m也是阻碍点 )

  
这样做充分利用了先取的消息,使每个悬线的拍卖时复杂度为O(1)。对于因点(i,j)为之的悬线对应之子矩形,它的面积也(right[i,j]-left[i,j])*height[i,j]。

这样结尾问题之散就是:

Result=max(right[i,j]-left[i,j])*height[i,j] (l<=i<n,
l<=j<=m)

满算法的时复杂度为O(NM),空间复杂度是O(NM)。

 

  两只算法的自查自纠:

以上说了区区种具有自然通用性的拍卖算法,时间复杂度分别吗O(S2)和O(NM)。两栽算法分别适用于不同之状。从时间复杂度上来拘禁,第一种算法对于障碍点稀疏的景比较可行,第二种植算法则与障碍点个数的有点并未一直的关系(当然,障碍点较少时好通过对障碍点坐标的离散化来弱化多少拍卖矩形的面积,不过这样于费心,不如第一种植算法好),适用于障碍点密集的气象。

 

这是近来经常出现的题材,例如冬令营2002之《奶牛浴场》,就属于最大子矩形问题。

五、   例题

拿前提出的个别种算法运用于现实的问题。

Winter Camp2002,奶牛浴场

1、    Winter Camp2002,奶牛浴场

分析

问题的数学模型就叫起一个矩形和矩形中之有障碍点,要求有矩形内的尽老起效子矩形。这多亏我们前所讨论的太大子矩形问题,因此前片种算法都适用于斯问题。

下分析两种植算法运用在主题上的优略:

对于第一种植算法,不用加其余的改动就好直接动用在马上道题上,时间复杂度为O(S2),S为障碍点个数;空间复杂度为O(S)。

对于第二栽算法,需要事先举行一定的先处理。由于第二栽算法复杂度与牛场的面积有关,而题材中牛场的面积大可怜(30000×30000),因此用针对数码进行离散化处理。离散化后矩形的轻重降呢S×S,所以时复杂度为O(S2),空间复杂度为O(S)。说明:需要留意的是,为了确保算法能是执行,在距散化的时光用丰富S个点,因此实际用之年华跟空间比较充分,而且编程较复杂。

起上述之辨析来拘禁,无论从时空效率要编程复杂度的角度来拘禁,这道题以第一栽算法都再优良。

题意简述:

2、    OIBH模拟赛1,提高组,Candy

题意简述:(原题见论文附件)

一个让分成 n*m 个格子的糖盒,第 i 行第 j 列位置的格子里面有 a[i,j]
颗糖。但糖果盒的部分格子被老鼠洗劫。现在需抢从夫糖果盒里面切割出一个矩形糖果盒,新的糖果盒不能够生洞,并且期待保留在新糖果盒内之香甜的总和尽量多。

参数约定:1 ≤ n,m ≤ 1000

 

分析

第一要小心的是:本题的范是一个矩阵,而休是矩形。在矩阵的情下,由于触及的个数是个别的,所以还要生出了一个新的问题:无限特别且值子矩阵

 

   定义:

   有效子矩阵呢中未含其他障碍点的子矩形。与有效子矩形不同,有效子矩阵地边界上呢非克包含障碍点。

有效子矩阵的权值(只有有效子矩形才生权值)为者子矩阵包含的所有点的权值和。

太充分权值有效子矩阵为所发发效子矩阵中权值最老的一个。以下简称为最好深且值子矩阵

 

主题的数学模型就是正权值条件下之极端老且值子矩阵问题。再同不善下极大化思想,因为矩阵中之权值都是刚刚的,所以最特别且值子矩阵一定是一个极大子矩阵。所以我们只是需要枚举所有的极大子矩阵,就能从中找到最好老且值子矩阵。同样,两栽算法就待稍加修改就足以解决本题。下面分析两种算法应用在主题上的优略:

对此第一种算法,由于矩形中障碍点的个数是勿确定的,而且极端深出或达N×M,这样时间复杂度有或上O(N2M2),空间复杂度为O(NM)。此外,由于矩形与矩阵的不等,所以当处理及会发生部分略带劳。

对第二栽算法,稍加变换就足以一直运用,时间复杂度为O(NM),空间复杂度为O(NM)。

 

可观看,第一种植算法并无入马上道题,因此最好好要利用第二栽算法。

John要以矩形牛场中建筑一个大型浴场,但是这巨型浴场不克包含其他一个奶牛的产奶点,但下奶点可以起在浴室的境界上。John的牛场和计划性之浴池都是矩形,浴场要全在牛场之内,并且浴场的轮廓要跟牛场的概况平行或者重合。要求所请浴场的面积尽可能大。

3、    Usaco Training, Section 1.5.4, BigBarn

题意简述(原题见论文附件)

      Farmer
John想以他的正方形农场及筑一个恰巧方形谷仓。由于农场上产生一对扶植,而且Farmer
John又无思剁这些树,因此如果找有尽酷之一个未分包任何树的等同片正方形场地。每棵树都得当一个沾。

参数约定:牛场为N×N的,树之棵数为T。N≤1000,T≤10000。

分析

    这题是矩形上的问题,但求的是最为大子正方形。首先,明确有定义。

1、定义有效子正方形呢里不包含其他障碍点的子正方形

2、定义庞有效子正方形否无可知再为外扩张的有效子正方形,一下简称极大子正方形

3、定义极致要命起效子正方形否所来来效子正方形中最好深的一个(或多个),以下简称绝大子正方形

 

主题的模子有部分特,要当一个带有一些障碍点的矩形中求无限大子正方形。这同前面少开的型是否出相似之处呢?还是于不过大子正方形的本来面目开始分析。

与前面的状况好像,利用极大化思想,我们得以博一个定律:

定理4】:在一个发障碍点的矩形中之最好特别出效子正方形一定是一个极大有效子正方形。

     

            
根据【定理4】,我们就需要枚举出所有的极大子正方形,就好从中寻找来最大子正方形。极大子正方形有啊特色也?所谓极大,就是休能够重新向他扩张。如果是极大子矩形,那么不可知再往他扩张的充要条件是四长边上还挂了障碍点(【定理2】)。类似之,我们得以知晓,一个有效子正方形是极大子正方形的充要条件是其任何两久相邻的滨还蒙了足足一个障碍点。根据当时一点,可以取一个重大之定律。

定理5】:每一个极大子正方形都至少被一个极大子矩形包含。且这个极大子正方形一定有些许条不相邻的边跟是蕴含它的极大子矩形的边重合。

 

因【定理5】,我们特需要枚举所有的极大子矩形,并检查其所包含的极大子正方形(一个极大子矩形包含的极大子正方形都是一模一样特别的)是否是太老之尽管好了。这样,问题的真相和前边所说之极端大子矩形问题是相同的,同样的,所利用的算法也是同样的。

盖算法1和算法2还枚举出了具有的极大子矩形,因此,算法1和算法2且足以用当主题上。具体的处理措施如下:对于每一个枚举出底极大子矩形,如图所示,如果它们的边长为a、b,那么它包含的极大子正方形的边长即为min(a,b)。

设想到N和T的分寸不一,所以不同之算法会有差之职能。下面分析两种植算法应用在主题上之优略。图片 9

对于第一栽算法,时间复杂度为O(T2),对于第二栽算法,时间复杂度为O(N2)。因为N<T,所以打日复杂度的角度看,第二种植算法要比第一种算法好。考虑到少只算法的空间复杂度都可以接受,所以选择第二种算法较好把。

以下是率先种与次种算法编程实现后每当USACO Training Program
Gateway上之运转时刻。可以望,在数量比较生时,算法2的频率比算法1强。

 

算法1:

Test  1:  0.009375

Test  2:  0.009375

Test  3:  0.009375

Test  4:  0.009375

Test  5:  0.009375

Test  6:  0.009375

Test  7:  0.021875

Test  8:     0.025

Test  9:  0.084375

Test 10:    0.3875

Test 11:     0.525

Test 12:    0.5625

Test 13:  0.690625

Test 14:   0.71875

Test 15:      0.75

算法2:

Test  1:  0.009375

Test  2:  0.009375

Test  3:  0.009375

Test  4:  0.009375

Test  5:  0.009375

Test  6:   0.00625

Test  7:  0.009375

Test  8:  0.009375

Test  9:    0.0125

Test 10:  0.021875

Test 11:  0.028125

Test 12:   0.03125

Test 13:   0.03125

Test 14:   0.03125

Test 15:  0.034375

 

如上,利用极大化思想与前面设计之有数独算法,通过变模型,解决了三个颇具一定代表性的例题。解题的关键就是安使用极大化思想进行模型转换和安抉择算法。

参数约定:产奶点的单数S不超越5000,牛场的限制N×M不超过30000×30000。

 六、小结

   
 设计算法要于问题之基本特征入手,找有解题的突破口。本文介绍了区区种适用于多数极大子矩形问题跟相关变更问题之算法,它们设计的突破口就是动了极大化思想,找到了枚举极大子矩形这种办法。

在效率及,两栽算法对于不同的情形各个有千秋。一个凡对准障碍点来设计的,因此复杂度与障碍点有关;另一个凡是本着任何矩形来统筹的,因此复杂度与矩形的面积有关。虽然简单单算法看起有巨大的反差,但她们之庐山真面目是相通的,都是使用极大化思想,从枚举所有的大有效子矩形入手,找有解决问题之法。

        

 需要专注的是,在缓解实际问题是单纯指套用一些存活算法是不够的,还欲针对题目开展宏观、透彻的解析,找来解题的突破口。

除此以外,如果用极大化思想,前面提到的一定量种植算法的复杂度已经不克再次下滑了,因为大有效子矩形的个数就是O(NM)或O(S2)的。如果利用其他算法,理论及是生或进一步提高算法效率,降低复杂度的。 

老二、 定义及认证

七、 附录:

      1、几单例题的原题。       
见舆论附件.doc

      2、例题的次序。           
见舆论附件.doc

证实:所有程序都以Free Pascal IDE for Dos, Version  0.9.2达标编译运行

第一明确有概念。

参考书目

1、     信息学奥林匹克竞赛指导

                         —-1997~1998竞技试题分析

            吴文虎 王建德 著

2、     IOI99中国集训队优秀论文集

3、     信息学奥林匹克(季刊)

4、     《金牌的路 竞赛辅导》 

江文哉主编  陕西师范大学出版社出版

 

原稿: 福州第三中学  王知昆

1、定义有效子矩形为中未含其他障碍点且边界及坐标轴平行的子矩形。如图所示,第一只是有效子矩形(尽管边界上产生障碍点),第二个未是有效子矩形(因为中间含有障碍点)。

2、极大有效子矩形:一个有效子矩形,如果未设有包含它还比她特别之有效子矩形,就如这有效子矩形为大有效子矩形。(为了叙述方便,以下称极大子矩形)

3、定义最可怜产生效子矩形为所发出发出效子矩形中极其深之一个(或多单)。以下简称为极端大子矩形。

其三、 极大化思想

【定理1】在一个产生障碍点的矩形中的最大子矩形一定是一个极大子矩形。

证明:如果尽特别子矩形A不是一个极大子矩形,那么根据极大子矩形的概念,存在一个暗含A且比A更怪之有效子矩形,这跟“A是最大子矩形”矛盾,所以【定理1】成立。

季、 从问题的性状入手,得到两种植常用之算法
定理1虽然很扎眼,但却是很重大之。根据定理1,我们得落如此一个解题思路:

由此枚举所有的极大子矩形,就可以找到最好大子矩形。下面根据是思路来计划算法。

预定:为了叙述方便,设尽矩形的大大小小也n×m,其中障碍点个数为s。

算法1

算法的思路是经过枚举所有的极大子矩形找有最好大子矩形。根据是思路好窥见,如果算法中有一致破枚举的子矩形不是有效子矩形、或者未是极大子矩形,那么好毫无疑问是算法做了“无用功”,这为即是用优化的地方。怎样保证每次枚举的还是极大子矩形呢,我们先行打极大子矩形的特点入手。

【定理2】:一个极大子矩形的季长边一定还不能够通往外扩张。更进一步地游说,一个有效子矩形是极大子矩形的充要条件是这子矩形的每条边或覆盖了一个障碍点,要么与整矩形的分界重合。

定理2的不错很肯定,如果一个有效子矩形的某某平长达边既没有遮盖一个障碍点,又没有同整矩形的边际重合,那么势必有一个饱含它的有效子矩形。根据定理2,我们得获取一个枚举极大子矩形的算法。为了处理好,首先以障碍点的集纳中增长整个矩形四竞赛上之触及。每次枚举子矩形的左右左右边际(枚举覆盖的障碍点),然后判断是否合法(内部是否发隐含障碍点)。这样的算法时间复杂度为O(S5),显然太强了。考虑到极大子矩形不可知包含障碍点,因此这样枚举4只边界显然会生出大量之无效子矩形。

设想只枚举左右边界的情事。对于早已规定的横边际,可以将持有处在此境界外的点按从上到下排序,如图1蒙受所展示,每一样羁绊就代表一个有效子矩形。这样做时间复杂度为O(S3)。由于保管每次得到的矩形都是法定的,所以枚举量比前同一栽算法小了成百上千。但用专注的凡,这样做枚举的子矩形虽然是法定的,然而不必然是大的。所以这算法还有优化的退路。通过对斯算法不足之处的优化,我们好取得一个快的算法。

回首上面的算法,我们好发现,所枚举的矩形的上下边界都埋了障碍点或者和合矩形的边际重合,问题不怕在左右边际上。只有那些左右疆也覆盖了障碍点或者和周矩形的界限重合的有效子矩形才是咱们得着眼之极大子矩形,所以前面的算法做了众多“无用功”。怎么压缩“无用功”呢,这里介绍一种植算法(算法1),它好用在众多此类题材上。

算法的笔触是这般的,先枚举极大子矩形的左边界,然后从左到右依次扫描每一个障碍点,并不断修改中之光景边界,从而枚举出所有因这一定为不当边界的极大子矩形。考虑而图2吃的老三独点,现在咱们若确定有坐1号点吧不当边界的庞大矩形。先用1哀号点右侧边的触及本横坐标排序。然后按从左到右的相继依次扫描1号点右侧边的接触,同时记录下时底卓有成效的前后边界。

起时令当前的前后边界分别吗一切矩形的内外边界。然后开扫描。第一不善遇到2声泪俱下点,以2如泣如诉点当右边界,结合当前之光景边界,就收获一个极大子矩形(如图3)。同时,由于所求矩形不克包含2如泣如诉点,且2号点当1号点之花花世界,所以要改时之下边界,即以2声泪俱下点之纵坐标作为新的脚界。第二软遇到3号沾,这时坐3哀号点之横坐标作为右边界又得取一个饱性1的矩形(如图4)。类似的,需要相应地改及边界。以此类推,如果此点是以当下接触(确定左边界的点)上方,则改达边界;如果在人世,则改下界;如果处在同一行,则可暂停搜索(因为后的矩形面积还是0了)。由于已于障碍点集合中增

如此做是不是用拥有的极大子矩形都枚举过了邪?可以窥见,这样做无非考虑到了错误边界覆盖一个碰之矩形,因此我们尚欲枚举左边界和合矩形的左边界重合的情景。这还好分成两类情况。一种植是漏洞百出边界和总体举行的左边界重合,而右侧边界覆盖了一个障碍点的图景,对于这种情况,可以据此类似之不二法门从右到左扫描每一个触及作为右边界的情状。另一样种植是反正界都和全矩形的横边界重合的状,对于当下好像情况我们好当事先处理着落成:先将所有点按纵坐标排序,然后可以取以邻两只点之纵坐标为上下边界,左右边界与任何矩形的左右边际重合的矩形,显然这样的矩形也是极大子矩形,因此为急需让枚举到。加了全副矩形右上比与右下角的鲜单点,所以无见面残留漏右边界及整矩形的右重合的极大子矩形(如图5)。需要专注的是,如果扫描到的点不以当下的光景边界外,那么尽管无欲针对之点进

行处理。

经前两步,可以枚举出所有的极大子矩形。算法1的年月复杂度是O(S2)。这样,可以化解大部分无比大子矩形和有关问题了。

尽管如此上述之算法(算法1)看起是比快之,但也出动的局限性。可以发现,这个算法的复杂度只同障碍点的个数s有关。但对于一些问题,s最酷产生或上n×m,当s较充分时,这个算法就不一定能满足时间及之求了。能否设计出一致种植据让n和m的算法也?这样于算法1免克奏效的时段咱们还有别的选择。我们又重于太核心的问题初步研究。

算法2

第一,根据定理1:最可怜起效子矩形一定是一个极大子矩形。不过同前面一模一样种算法不同的凡,我们不再要求各个一样赖枚举的自然是极大子矩形而只要求具备的极大子矩形都于枚举到。看起这种算法可能较前无异种不同,其实不然,因为前面同栽算法并无是宏观的:虽然每次考察的都是极大子矩形,但它们要做了少的“无用功”。可以窥见,当障碍点很密集的时,前同一栽算法会做大量未曾因此的较工作。要化解之题目,我们亟须跳出前面的笔触,重新考虑一个新的算法。注意到极大子矩形的个数不会见超过矩形内单位方格的个数,因此我们出或找来同种时光复杂度是O(N×M)的算法。

定义:

中竖线:除了少单端点外,不蒙任何障碍点的竖直线段。

悬线:上端点覆盖了一个障碍点或达全部矩形上捧的实惠竖线。如图所示的老三独有效竖线都是悬线。

对此其余一个极大子矩形,它的达到边界及或生一个障碍点,要么和总体矩形的达边界重合。那么要拿一个极大子矩形按x坐标不同切割成多单(实际上是不少只)与y轴垂直的线,则中肯定有一样长长的悬线。而且同长条悬线通过尽可能地向左右运动恰好能取得一个子矩形(未必是极大子矩形,但只有或向下扩展)。通过上述之辨析,我们得落一个重点的定律。

【定理3】:如果用一个悬线向左右星星独趋势尽可能移动所获取的有效子矩形称为这个悬线所对应的子矩形,那么所有悬线所对应之有效子矩形的会师一定带有了有极大子矩形的集聚。

定理3蒙的“尽可能”移动指的是挪及一个障碍点或者矩形边界的职位。

依据【定理3】可以发现,通过枚举所有的悬线,就足以枚举出所有的极大子矩形。由于每个悬线都跟它们底部的大点一一对应,所以悬线的个数=(n-1)×m(以矩形中除去顶部的触及之外的每个点啊底,都得获一个悬线,且尚未遗漏)。如果能得对每个悬线的操作时还为O(1),那么一切算法的复杂度就是O(NM)。这样,我们看出了缓解问题之想望。

现今之题目是,怎样在O(1)的流年外完成对每个悬线的操作。我们了解,每个极大子矩形都好经过一个悬线左右走得到。所以,对于每个确定了脚的悬线,我们得理解有关于它的老三单量:顶部、左右最多能移动至的位置。对于底部也(i,j)的悬线,设它的高为hight[i,j],左右绝多会活动至之职务也left[i,j],right[i,j]。为了充分利用以前获得的音,我们拿即时三独函数用递推的形式被闹。

对以碰(i,j)为根的悬线:

如若接触(i-1,j)为障碍点,那么,显然以(i,j)为的之悬线高度也1,而且左右都可以倒至整个矩形的左右界,即

height[i,j]=l

left[i,j]=0

right[i,j]=m

假使点(i-1,j)不是障碍点,那么,以(i,j)为之的悬线就等为(i-1,j)为底之悬线+点(i,j)到点(i-1,j)的线。因此,height[i,j]=height[i-1,j]+1。比较辛苦的凡左右疆,先考虑left[i,j]。如下图所示,(i,j)对应之悬线左右能够移动的岗位而当(i-1,j)的基本功及别。

即left[i,j]=max( left[i-1,j] , (i-1,j)左边第一只障碍点位置 ) 如图

right[i,j]的求法类似。综合起来,可以抱及时三单参数的递给推式:

height[i,j]=height[i-1,j]+1

left[i,j]=max( left[i-1,j] ,
(i-1,j)左边第一个障碍点位置,边界0也是阻碍点 )

right[i,j]=max( right[i-1,j] ,
(i-1,j)右边第一只障碍点位置,边界m也是阻碍点 )

如此这般做充分利用了以前取的信息,使每个悬线的拍卖时复杂度为O(1)。对于坐点(i,j)为的的悬线对应的子矩形,它的面积也(right[i,j]-left[i,j])*height[i,j]。

然结尾问题之消除就是:

Result=max(right[i,j]-left[i,j])*height[i,j] (l<=i<n,
l<=j<=m)

整整算法的日复杂度为O(NM),空间复杂度是O(NM)。

零星独算法的对照:

以上说了少种植具有一定通用性的处理算法,时间复杂度分别吗O(S2)和O(NM)。两种植算法分别适用于不同的景象。从岁月复杂度上来拘禁,第一栽算法对于障碍点稀疏的情况较实用,第二种算法则跟障碍点个数的有些并未直接的涉(当然,障碍点较少时可透过对障碍点坐标的离散化来减多少拍卖矩形的面积,不过这样比较麻烦,不如第一种算法好),适用于障碍点密集的状况。

五、 例题

将前提出的一定量栽算法运用于实际的题材。
1、 Winter Camp2002,奶牛浴场

分析:

题材的数学模型就让有一个矩形和矩形中之有障碍点,要求有矩形内的无比深起效子矩形。这多亏我们前所讨论的最好大子矩形问题,因此前片种植算法都适用于斯题目。

下面分析两栽算法运用在主题上之优略:

对此第一栽算法,不用加其它的修改就可以一直行使在马上道题上,时间复杂度为O(S2),S为障碍点个数;空间复杂度为O(S)。

对第二种植算法,需要事先开一定的先期处理。由于第二栽算法复杂度与牛场的面积有关,而题材中牛场的面积大可怜(30000×30000),因此用针对数码进行离散化处理。离散化后矩形的轻重降为S×S,所以时复杂度为O(S2),空间复杂度为O(S)。说明:需要留意的凡,为了确保算法能科学执行,在距离散化的早晚用添加S个点,因此实际得之时间和空间比较生,而且编程较复杂。

从以上的分析来拘禁,无论由时空效率要编程复杂度的角度来拘禁,这道题利用第一种植算法都再度漂亮。
2、 OIBH模拟赛1,提高组,Candy

题意简述:(原题见论文附件)

一个给分成 n*m 个格子的糖盒,第 i 行第 j 列位置的格子里面来 a[i,j]
颗糖。但糖果盒的片格子被老鼠洗劫。现在待尽早从这糖果盒里面切割出一个矩形糖果盒,新的糖盒不能够发洞,并且希望保留在初糖果盒内的甜的总额尽量多。

参数约定:1 ≤ n,m ≤ 1000

分析

先是需专注的是:本题的模型是一个矩阵,而未是矩形。在矩阵的场面下,由于触及的个数是简单的,所以还要发了一个新的题目:最可怜且值子矩阵。

定义:

有效子矩阵为中未分包其他障碍点的子矩形。与有效子矩形不同,有效子矩阵地边界上啊非能够包含障碍点。

有效子矩阵的权值(只有有效子矩形才发权值)为夫子矩阵包含的所有点的权值和。

极酷权值有效子矩阵为所发出起效子矩阵中权值最特别之一个。以下简称为极端充分且值子矩阵。

主题的数学模型就是正权值条件下的不过充分且值子矩阵问题。再同次采用极大化思想,因为矩阵中之权值都是刚之,所以最好老且值子矩阵一定是一个极大子矩阵。所以我们才需要枚举所有的极大子矩阵,就能从中找到最好特别且值子矩阵。同样,两种植算法就待稍加修改就好缓解本题。下面分析两栽算法应用在主题上之优略:

对于第一种算法,由于矩形中障碍点的个数是无确定的,而且最好可怜起或达成N×M,这样时间复杂度有或达到O(N2M2),空间复杂度为O(NM)。此外,由于矩形与矩阵的例外,所以在处理上会有有略劳。

对第二种植算法,稍加变换就好直接下,时间复杂度为O(NM),空间复杂度为O(NM)。

得视,第一栽算法并无适合当下道题,因此最好好要用第二种植算法。
3、 Usaco Training, Section 1.5.4, BigBarn

题意简述(原题见论文附件)

  Farmer John想在他的正方形农场上建一个正方形谷仓。由于农场上有一些树,而且Farmer John又不想砍这些树,因此要找出最大的一个不包含任何树的一块正方形场地。每棵树都可以看成一个点。

参数约定:牛场为N×N的,树之棵数为T。N≤1000,T≤10000。

分析:

立马题是矩形上之题目,但要求的是最好大子正方形。首先,明确有定义。

1、定义有效子正方形为里不分包其他障碍点的子正方形

2、定义极大有效子正方形为无可知重朝着外扩张的有效子正方形,一下简称极大子正方形

3、定义最深产生效子正方形为所发出发出效子正方形中尽特别之一个(或多单),以下简称最大子正方形。

主题的范有一部分特殊,要在一个暗含一些障碍点的矩形中要最好大子正方形。这与前方少挥毫之范是否生相似之处呢?还是从最大子正方形的本色开始分析。

暨前方的状况好像,利用极大化思想,我们得以收获一个定律:

【定理4】:在一个起障碍点的矩形中之无比要命起效子正方形一定是一个庞大有效子正方形。

冲【定理4】,我们一味待枚举出所有的极大子正方形,就好从中寻找有无限大子正方形。极大子正方形有什么特点呢?所谓极大,就是不能够再于他扩展。如果是极大子矩形,那么非可知更朝着外扩展的充要条件是四长边上还覆盖了障碍点(【定理2】)。类似的,我们得以清楚,一个有效子正方形是极大子正方形的充要条件是其任何两久相邻之边缘还埋了至少一个障碍点。根据当下一点,可以博得一个主要之定律。

【定理5】:每一个极大子正方形都至少被一个极大子矩形包含。且是极大子正方形一定生少修未相邻之底限与此蕴藏它的极大子矩形的边重合。

根据【定理5】,我们只待枚举所有的极大子矩形,并检讨她所蕴涵的极大子正方形(一个极大子矩形包含的极大子正方形都是一样特别之)是否是绝深之便好了。这样,问题之庐山真面目和眼前所说的绝大子矩形问题是平的,同样的,所利用的算法为是一模一样的。

为算法1和算法2且枚举出了有着的极大子矩形,因此,算法1和算法2都可据此当主题上。具体的拍卖措施如下:对于各一个枚举出之极大子矩形,如图所示,如果它的边长为a、b,那么它蕴含的极大子正方形的边长即为min(a,b)。

设想到N和T的高低不同,所以不同之算法会有异之作用。下面分析两栽算法应用在主题上之优略。

于第一种算法,时间复杂度为O(T2),对于第二栽算法,时间复杂度为O(N2)。因为N<T,所以打岁月复杂度的角度看,第二栽算法要于第一栽算法好。考虑到片单算法的半空中复杂度都得以领,所以选择第二栽算法较好把。

以下是第一栽及第二种植算法编程实现后以USACO Training Program
Gateway上之周转时。可以看到,在数码较充分时,算法2的效率比算法1强。

算法1:

Test 1: 0.009375

Test 2: 0.009375

Test 3: 0.009375

Test 4: 0.009375

Test 5: 0.009375

Test 6: 0.009375

Test 7: 0.021875

Test 8: 0.025

Test 9: 0.084375

Test 10: 0.3875

Test 11: 0.525

Test 12: 0.5625

Test 13: 0.690625

Test 14: 0.71875

Test 15: 0.75

算法2:

Test 1: 0.009375

Test 2: 0.009375

Test 3: 0.009375

Test 4: 0.009375

Test 5: 0.009375

Test 6: 0.00625

Test 7: 0.009375

Test 8: 0.009375

Test 9: 0.0125

Test 10: 0.021875

Test 11: 0.028125

Test 12: 0.03125

Test 13: 0.03125

Test 14: 0.03125

Test 15: 0.034375

以上,利用极大化思想与前面设计之点滴独算法,通过变模型,解决了三单颇具自然代表性的例题。解题的重要就是是如何利用极大化思想进行模型转换和什么选择算法。
六、小结

 设计算法要从问题的基本特征入手,找出解题的突破口。本文介绍了两种适用于大部分最大子矩形问题及相关变型问题的算法,它们设计的突破口就是利用了极大化思想,找到了枚举极大子矩形这种方法。

在效率达,两种植算法对于不同的事态各个有千秋。一个是指向障碍点来统筹的,因此复杂度与障碍点有关;另一个凡对准任何矩形来计划的,因此复杂度与矩形的面积有关。虽然少独算法看起有巨大的出入,但她俩之本色是相通的,都是采取极大化思想,从枚举所有的大有效子矩形入手,找有解决问题之艺术。

用留意的凡,在解决实际问题是就靠套用一些存世算法是不够的,还得针对问题进行完美、透彻的剖析,找有解题的突破口。

除此以外,如果以极大化思想,前面提到的个别种算法的复杂度已经休能够重复下降了,因为大有效子矩形的个数就是O(NM)或O(S2)的。如果采用其它算法,理论及是起或进一步提高算法效率,降低复杂度的。
七、 附录:

1、几单例题的原题。 见论文附件.doc

2、例题的次序。 见论文附件.doc

说明:所有程序都于Free Pascal IDE for Dos, Version 0.9.2臻编译运行
参考书目

1、 信息学奥林匹克竞赛指导

—-1997~1998斗试题分析

吴文虎 王建德 著

2、 IOI99中国集训队优秀论文集

3、 信息学奥林匹克(季刊)

4、 《金牌的路 竞赛辅导》

江文哉主编 陕西师范大学出版社出版

原文: 福州第三中学 王知昆

相关文章