国家集训队2003论文集 王知昆

《国家集训队2003论文集 王知昆》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、王知昆第10页IOI2003国家集训队论文浅谈用极大化思想解决最大子矩形问题福州第三中学王知昆【摘要】本文针对一类近期经常出现的有关最大（或最优）子矩形及相关变形问题，介绍了极大化思想在这类问题中的应用。分析了两个具有一定通用性的算法。并通过一些例题讲述了这些算法选择和使用时的一些技巧。【关键字】矩形，障碍点，极大子矩形【正文】一、问题最大子矩形问题：在一个给定的矩形网格中有一些障碍点，要找出网格内部不包含任何障碍点，且边界与坐标轴平行的最大子矩形。这是近期经常出现的问题，例如冬令营2002的《奶牛浴场》，就属于最大子

2、矩形问题。WinterCamp2002,奶牛浴场题意简述：（原题见论文附件）John要在矩形牛场中建造一个大型浴场，但是这个大型浴场不能包含任何一个奶牛的产奶点，但产奶点可以出在浴场的边界上。John的牛场和规划的浴场都是矩形，浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。要求所求浴场的面积尽可能大。参数约定：产奶点的个数S不超过5000,牛场的范围N×M不超过30000×30000。二、定义和说明首先明确一些概念。1、定义有效子矩形为内部不包含任何障碍点且边界与坐标轴平行的子矩形。如图所示，第一个

3、是有效子矩形（尽管边界上有障碍点），第二个不是有效子矩形（因为内部含有障碍点）。王知昆第10页IOI2003国家集训队论文1、极大有效子矩形：一个有效子矩形，如果不存在包含它且比它大的有效子矩形，就称这个有效子矩形为极大有效子矩形。（为了叙述方便，以下称为极大子矩形）2、定义最大有效子矩形为所有有效子矩形中最大的一个（或多个）。以下简称为最大子矩形。二、极大化思想【定理1】在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。证明：如果最大子矩形A不是一个极大子矩形，那么根据极大子矩形的定义，存在一个包含A且比A更大

4、的有效子矩形，这与“A是最大子矩形”矛盾，所以【定理1】成立。三、从问题的特征入手，得到两种常用的算法定理1虽然很显然，但却是很重要的。根据定理1，我们可以得到这样一个解题思路：通过枚举所有的极大子矩形，就可以找到最大子矩形。下面根据这个思路来设计算法。约定：为了叙述方便，设整个矩形的大小为n×m，其中障碍点个数为s。算法1算法的思路是通过枚举所有的极大子矩形找出最大子矩形。根据这个思路可以发现，如果算法中有一次枚举的子矩形不是有效子矩形、或者不是极大子矩形，那么可以肯定这个算法做了“无用功”，这也就是需要优化的地方。

5、怎样保证每次枚举的都是极大子矩形呢，我们先从极大子矩形的特征入手。【定理2】：一个极大子矩形的四条边一定都不能向外扩展。更进一步地说，一个有效子矩形是极大子矩形的充要条件是这个子矩形的每条边要么覆盖了一个障碍点，要么与整个矩形的边界重合。王知昆第10页IOI2003国家集训队论文定理2的正确性很显然，如果一个有效子矩形的某一条边既没有覆盖一个障碍点，又没有与整个矩形的边界重合，那么肯定存在一个包含它的有效子矩形。根据定理2，我们可以得到一个枚举极大子矩形的算法。为了处理方便，首先在障碍点的集合中加上整个矩形四角上的点。

6、每次枚举子矩形的上下左右边界（枚举覆盖的障碍点），然后判断是否合法（内部是否有包含障碍点）。这样的算法时间复杂度为O(S5)，显然太高了。考虑到极大子矩形不能包含障碍点，因此这样枚举4个边界显然会产生大量的无效子矩形。考虑只枚举左右边界的情况。对于已经确定的左右边界，可以将所有处在这个边界内的点按从上到下排序，如图1中所示，每一格就代表一个有效子矩形。这样做时间复杂度为O(S3)。由于确保每次得到的矩形都是合法的，所以枚举量比前一种算法小了很多。但需要注意的是，这样做枚举的子矩形虽然是合法的，然而不一定是极大的。所以这

7、个算法还有优化的余地。通过对这个算法不足之处的优化，我们可以得到一个高效的算法。回顾上面的算法，我们不难发现，所枚举的矩形的上下边界都覆盖了障碍点或者与整个矩形的边界重合，问题就在于左右边界上。只有那些左右边界也覆盖了障碍点或者与整个矩形的边界重合的有效子矩形才是我们需要考察的极大子矩形，所以前面的算法做了不少“无用功”。怎么减少“无用功”呢，这里介绍一种算法（算法1），它可以用在不少此类题目上。算法的思路是这样的，先枚举极大子矩形的左边界，然后从左到右依次扫描每一个障碍点，并不断修改可行的上下边界，从而枚举出所有以这

8、个定点为左边界的极大子矩形。考虑如图2中的三个点，现在我们要确定所有以1号点为左边界的极大矩形。先将1号点右边的点按横坐标排序。然后按从左到右的顺序依次扫描1号点右边的点，同时记录下当前的可行的上下边界。王知昆第10页IOI2003国家集训队论文开始时令当前的上下边界分别为整个矩形的上下边界。然后开始扫描。第一次遇到2号点，以2号