五、 例题 将前面提出的两种算法运用于具体的问题。 1、 Winter Camp2002,奶牛浴场 分析： 题目的数学模型就是给出一个矩形和矩形中的一些障碍点，要求出矩形内的{zd0}有效子矩形。这正是我们前面所讨论的{zd0}子矩形问题，因此前两种算法都适用于这个问题。 下面分析两种算法运用在本题上的优略： 对于{dy}种算法，不用加任何的修改就可以直接应用在这道题上，时间复杂度为O(S2)，S为障碍点个数；空间复杂度为O(S)。 对于第二种算法，需要先做一定的预处理。由于第二种算法复杂度与牛场的面积有关，而题目中牛场的面积很大（30000×30000），因此需要对数据进行离散化处理。离散化后矩形的大小降为S×S，所以时间复杂度为O(S2)，空间复杂度为O(S)。说明：需要注意的是，为了保证算法能正确执行，在离散化的时候需要加上S个点，因此实际需要的时间和空间较大，而且编程较复杂。 从以上的分析来看，无论从时空效率还是编程复杂度的角度来看，这道题采用{dy}种算法都更优秀。 2、 OIBH模拟赛1,提高组，Candy 题意简述：（原题见论文附件） 一个被分为 n*m 个格子的糖果盒，第 i 行第 j 列位置的格子里面有 a [i,j] 颗糖。但糖果盒的一些格子被老鼠洗劫。现在需要尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且希望保留在新糖果盒内的糖的总数尽量多。 参数约定：1 ≤ n，m ≤ 1000 分析 首先需要注意的是：本题的模型是一个矩阵，而不是矩形。在矩阵的情况下，由于点的个数是有限的，所以又产生了一个新的问题：{zd0}权值子矩阵。 定义： 有效子矩阵为内部不包含任何障碍点的子矩形。与有效子矩形不同，有效子矩阵地边界上也不能包含障碍点。 有效子矩阵的权值（只有有效子矩形才有权值）为这个子矩阵包含的所有点的权值和。 {zd0}权值有效子矩阵为所有有效子矩阵中权值{zd0}的一个。以下简称为{zd0}权值子矩阵。 本题的数学模型就是正权值条件下的{zd0}权值子矩阵问题。再一次利用极大化思想，因为矩阵中的权值都是正的，所以{zd0}权值子矩阵一定是一个极大子矩阵。所以我们只需要枚举所有的极大子矩阵，就能从中找到{zd0}权值子矩阵。同样，两种算法只需稍加修改就可以解决本题。下面分析两种算法应用在本题上的优略： 对于{dy}种算法，由于矩形中障碍点的个数是不确定的，而且{zd0}有可能达到N×M,这样时间复杂度有可能达到O(N2M2)，空间复杂度为O(NM)。此外，由于矩形与矩阵的不同，所以在处理上会有一些小麻烦。 对于第二种算法，稍加变换就可以直接使用，时间复杂度为O(NM),空间复杂度为O（NM）。 可以看出，{dy}种算法并不适合这道题，因此{zh0}还是采用第二种算法。 3、 Usaco Training, Section 1.5.4, Big Barn 题意简述（原题见论文附件） Farmer John想在他的正方形农场上建一个正方形谷仓。由于农场上有一些树，而且Farmer John又不想砍这些树，因此要找出{zd0}的一个不包含任何树的一块正方形场地。每棵树都可以看成一个点。 参数约定：牛场为N×N的，树的棵数为T。N≤1000,T≤10000。 分析： 这题是矩形上的问题，但要求的是{zd0}子正方形。首先，明确一些概念。 1、定义有效子正方形为内部不包含任何障碍点的子正方形 2、定义极大有效子正方形为不能再向外扩展的有效子正方形，一下简称极大子正方形 3、定义{zd0}有效子正方形为所有有效子正方形中{zd0}的一个（或多个），以下简称{zd0}子正方形。 本题的模型有一些特殊，要在一个含有一些障碍点的矩形中求{zd0}子正方形。这与前两题的模型是否有相似之处呢？还是从{zd0}子正方形的本质开始分析。 与前面的情况类似，利用极大化思想，我们可以得到一个定理： 【定理4】：在一个有障碍点的矩形中的{zd0}有效子正方形一定是一个极大有效子正方形。 根据【定理4】,我们只需要枚举出所有的极大子正方形，就可以从中找出{zd0}子正方形。极大子正方形有什么特征呢？所谓极大，就是不能再向外扩展。如果是极大子矩形，那么不能再向外扩展的充要条件是四条边上都覆盖了障碍点（【定理2】）。类似的，我们可以知道，一个有效子正方形是极大子正方形的充要条件是它任何两条相邻的边上都覆盖了至少一个障碍点。根据这一点，可以得到一个重要的定理。 【定理5】：每一个极大子正方形都至少被一个极大子矩形包含。且这个极大子正方形一定有两条不相邻的边与这个包含它的极大子矩形的边重合。 根据【定理5】,我们只需要枚举所有的极大子矩形，并检查它所包含的极大子正方形（一个极大子矩形包含的极大子正方形都是一样大的）是否是{zd0}的就可以了。这样，问题的实质和前面所说的{zd0}子矩形问题是一样的，同样的，所采用的算法也是一样的。 因为算法1和算法2都枚举出了所有的极大子矩形，因此，算法1和算法2都可以用在本题上。具体的处理方法如下：对于每一个枚举出的极大子矩形，如图所示，如果它的边长为a、b，那么它包含的极大子正方形的边长即为min(a,b)。 对于{dy}种算法，时间复杂度为O(T2)，对于第二种算法，时间复杂度为O(N2)。因为N<T，所以从时间复杂度的角度看，第二种算法要比{dy}种算法好。考虑到两个算法的空间复杂度都可以承受，所以选择第二种算法较好些。 以下是{dy}种和第二种算法编程实现后在USACO Training Program Gateway上的运行时间。可以看出，在数据较大时，算法2的效率比算法1高。
以上，利用极大化思想和前面设计的两个算法，通过转换模型，解决了三个具有一定代表性的例题。解题的关键就是如何利用极大化思想进行模型转换和如何选择算法。 五、小结 设计算法要从问题的基本特征入手，找出解题的突破口。本文介绍了两种适用于大部分{zd0}子矩形问题及相关变型问题的算法，它们设计的突破口就是利用了极大化思想，找到了枚举极大子矩形这种方法。 在效率上，两种算法对于不同的情况各有千秋。一个是针对障碍点来设计的，因此复杂度与障碍点有关；另一个是针对整个矩形来设计的，因此复杂度与矩形的面积有关。虽然两个算法看起来有着巨大的差别，但他们的本质是相通的，都是利用极大化思想，从枚举所有的极大有效子矩形入手，找出解决问题的方法。 需要注意的是，在解决实际问题是仅靠套用一些现有算法是不够的，还需要对问题进行全面、透彻的分析,找出解题的突破口。 此外，如果采用极大化思想，前面提到的两种算法的复杂度已经不能再降低了，因为极大有效子矩形的个数就是O(NM)或O(S2)的。如果采用其他算法，理论上是有可能进一步提高算法效率，降低复杂度的。 |
