USACO/rectbarn

来自NOCOW

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 6 .1中的OI题目A Rectangular Barn的介绍及题解，参见翻译，C语言代码，C++语言代码，Pascal语言代码。

[编辑] 问题分析

本题是求一个没有损坏区域的最大子矩阵。显然要用DP来做。当然，由于本题是矩形，所以big barn的方法就无法用到这里了。现在我们换一种思路。如果找到一个点，把这个点向上、左、右三个方向扩展，那么统计扩展出来的尽可能大的矩形就行了。看起来这种算法的时间复杂度很高，这也正是DP的用处——解决大量重复子问题。否则这样的算法就成了枚举了。

[编辑] 算法

[编辑] DP

设h[i,j]为点(i,j)向上方扩展的最大高度，l[i,j]为(i,h[i,j])这条线段向左边扩展的最长距离，r[i,j]为(i,h[i,j])向右边扩展的最长距离。转移方程：

其中，tl表示点(i,j)向左扩展的最大距离，tr表示点(i,j)向右扩展的最大距离。

实现的时候有一个技巧：不用把整个图用一个二维数组表示出来，因为损坏点是很稀疏的。直接用一个数组保存点的坐标，然后离散化一下，这样可以很方便地找到每行的最长无损坏区间，这个区间内的所有点的数据都可以在O(1)时间内计算出来。用这种方法可以节省很多空间。上述算法时间复杂度为O(RC)，空间复杂度为O(max(p,r,c))。

[编辑] 枚举

本题应该是利用极大矩阵思路，即求出所有的矩阵，然后找到最大值，而此题的关键就是怎样找所有的矩阵.

显然此题我们应该找到一种效率高于O(n^2*logn)的算法，要不然会超时。

上面的算法效率比较高，usaco上最后一个测试数据用了0.588s

[编辑] 极大化思想

参见2003年国家集训队，王知昆论文。复杂度O（N^2)。

ps:路人走过。话说这个复杂度不应该是O(NM)的吗？论文中还有一个适合稀疏图的O(S^2)方法呢，不过不适合这题……

[编辑] 路径压缩

注意USACO的内存限制比较严格,需要用滚动数组.

[编辑] 最大子矩形

这道题初看很想Big Barn，我也尝试用类似的方法做，后来发现这条路走不通。重新考虑: 对于任意一个矩形，如果它的四边都不能继续扩展（碰到边界或坏点），则此矩形为极大矩形。显然，所求的最大矩形一定是极大矩形。对于任意一个点(i,j)，我们向上找到一个坏点或边界(k,j)，得到线段(k,j)-(i,j)，我们把线段向左右两边扩展，直到不能扩展为止。此时得到的矩形在上边和左右两边都不能扩展了。我们只要枚举每个点(i,j)，计算它依照上述方法扩展的矩形的面积，取其中最大的一个就是所求。考虑动态规划：设h[i,j]表示点(i,j)向上扩展的最大距离，l[i,j]，r[i,j]分别表示所得线段向左右扩展的最大距离，此时矩形的面积

S=h[i,j]×(l[i,j]+r[i,j]-1)。
h[i,j]=h[i-1,j]+1               (i,j)是好点
 0                               (i,j)是坏点 
l[i,j]=min(l[i-1,j],tl[i,j])    (i,j)是好点
 ∞                                   (i,j)是坏点 
r[i,j]=min(r[i-1,j],tr[i,j])    (i,j)是好点
 ∞                                   (i,j)是坏点

其中tl[i,j]，tr[i,j]分别是(i,j)向左右扩展的最大距离。时间复杂度是O(RC)。根据状态转移方程的特点，我们只需要用一维数组记录状态即可，空间复杂度是O(max(R,C))。参考文献：《浅谈用极大化思想解决最大子矩形问题》，作者：王知昆。

 by--wh硕

[编辑] 用栈实现比较好

保证栈的单调性，退栈的时候进行计算 ——by pty

[编辑] 另一种思路

我看到这道题，想到了一种O(NM^2)的算法。假设一条扫描线从上到下扫描，对于每一行，我们枚举这一行上的每个点，计算出以这个点为子矩阵的左下角所能形成的所有矩形的面积。具体实现时，对于第i列维护一个域Up[i]，表示当前行的第i个点向上最多延伸i个单位。则Up[i] = Up[i -　1] + 1(if i hasn't been damaged); otherwise, Up[i] = 0.这样，可以在O(M)的时间内计算出这一行所有点的Up值。于是，在枚举得到左下角i后,我们枚举j为矩阵的右下角，则此时矩阵面积Area = (j - i + 1) * min(Up[i]..Up[j]). 后者可以在j向右延伸时顺便更新。这样，我们便得到了一个O(NM^2)的算法了。然而，这个算法只通过了前7个点，我们还需要进一步的剪枝。我想到了3个剪枝(实际上只添加了3句话)，达到了这样的效果： Executing...

  Test 1: TEST OK [0.000 secs, 3284 KB]
  Test 2: TEST OK [0.000 secs, 3284 KB]
  Test 3: TEST OK [0.011 secs, 3284 KB]
  Test 4: TEST OK [0.011 secs, 3284 KB]
  Test 5: TEST OK [0.022 secs, 3284 KB]
  Test 6: TEST OK [0.032 secs, 3284 KB]
  Test 7: TEST OK [0.108 secs, 3284 KB]
  Test 8: TEST OK [0.572 secs, 3284 KB]
  Test 9: TEST OK [0.875 secs, 3284 KB]
  Test 10: TEST OK [0.886 secs, 3284 KB]

a.最优性剪枝：当我们枚举左下角i时，if (Up[i] *(m - i + 1) <= BestAnsNow) continue;

b.避免浪费性剪枝：维护一个域(bool)Start[i]表示第i列作为起点是否有意义。显然，if (Up[i-1] >= Up[i]) 那么，枚举第i个点就已经不可能是最优解了。

c.避免重复性剪枝：仔细观察发现，如果我们在计算以i为起点，枚举到j时，出现了Up[j] <= Up[i-1]的情况，那么就没有必要接着向右延伸而可以直接break了（我相信大家都能明白，就不解释了）。通过这几个小优化，就可以通过了，代码也不长（其实，我觉得这道题主要是考快排），参见c++程序(abcde-11)。

            by Ever_ljq

[编辑] 参考代码

C

C++

Pascal