悬线法及后缀最小值|笔记

悬线法及后缀最小值|笔记

六月 15, 2018

给一个01矩阵,求面积最大的只含有1的子矩形和正方形

定义

对于一个包含障碍的矩阵,从一个点出发向四周能扩展到的最大的矩形称为极大子矩形,显然极大子矩形的四条边上都至少有一个障碍物.所有极大子矩形中面积最大的成为最大子矩形.

最大子正方形

只是求最大子正方形可以设计一个DP解法

设dp(x,y)为以(x,y)为右下角的最大正方形

dp(x,y) = min(dp(x - 1,y) , dp(x,y - 1) , dp(x - 1,y - 1)) + 1

但是DP解法无法处理最大子矩形,因此需要悬线法

悬线法

悬线法是一个求极大子矩形的算法

操作方式

对于一个点(x,y) ,从此处向上划一条线直到碰到障碍,记长度为d(x,y),接着将该线向左,向右扫描,直到碰到障碍

注意: 这个扫描得到的矩形未必是极大子矩形,因为其下边界未必触及障碍.但它随后一定会成为一个极大子矩形的子矩形,不会出现遗漏

以上操作进一步抽象如下:

对第x行的数列d(x),求每一个元素d(x,y)作为前缀最小值和后缀最小值时最长的子列长度right(x,y),left(x,y).该矩形面积为d(x,y) * (right(x,y) + left(x,y) - 1)

d(x,y)的维护可以通过动态规划实现,维护复杂度为O(1),同时可以使用滚动数组优化.

那么如何实现平均O(1)维护后缀最小值数组?

后缀最小值

对于点(x,y),朴素维护其后缀最小值数组即询问它之前的每一个元素即d(x,y - k),0 < k <= y是否小于d(x,y) . 复杂度高达O(n)

注意:若一个元素d(x,j) <= d(x,y),则显而易见(x,j)的后缀最小值数组一定能成为(x,y)的后缀最小值数组的一部分,可以直接跳过这一段的询问.若d(x,j) > d(x,y),则询问到此为止,无需向前询问.

由此可以得到两个结论:

  1. 所有询问中每个元素只需肯定回答一次
  2. 每个元素发出的询问只会得到一个否定回答

询问次数最多为2*n,时间复杂度为O(1)

相关题目

USACO5.3巨大的牛棚

农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定,他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出,在他的农场中,不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。

EXAMPLE

考虑下面的方格,它表示农夫约翰的农场,‘.’表示没有树的方格,‘#’表示有树的方格


1 2 3 4 5 6 7 8

1 . . . . . . . .

2 . # . . . # . .

3 . . . . . . . .

4 . . . . . . . .

5 . . . . . . . .

6 . . # . . . . .

7 . . . . . . . .

8 . . . . . . . .


最大的牛棚是 5 x 5 的,可以建造在方格右下角的两个位置其中一个。

ZJOI2007棋盘制作

国际象棋是世界上最古老的博弈游戏之一,和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想,棋盘是一个 8×8 大小的黑白相间的方阵,对应八八六十四卦,黑白对应阴阳。

而我们的主人公小Q,正是国际象棋的狂热爱好者。作为一个顶尖高手,他已不满足于普通的棋盘与规则,于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。

小Q找到了一张由 N×M 个正方形的格子组成的矩形纸片,每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘,当然,他希望这个棋盘尽可能的大。

不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘(当然,不管哪种,棋盘必须都黑白相间,即相邻的格子不同色),所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积,从而决定哪个更好一些。

于是小Q找到了即将参加全国信息学竞赛的你,你能帮助他么?

        for (int i = 1;i <= n;++ i){
                for (int j = 1;j <= m;++ j){
                        dp[j] = (dp[j] + 1 ) *  map_[i][j];//map_表示输入地图
                        if(!dp[j]){
                                l[j] = 0;
                                continue;
                        }
                        int k = j - 1;
                        while (dp[k] >= dp[j])
                                k = k - l[k];
                        l[j] = j - k;
                }
                for (int j = m;j >= 1;-- j){
                        if(!dp[j]){
                                r[j] = 0;
                                continue;
                        }
                        int k = j + 1;
                        while (dp[k] >= dp[j])
                                k = k + r[k];
                        r[j] = k - j;
                        ans1 = max(ans1,min(r[j] + l[j] - 1,dp[j]));//正方形
                        ans2 = max(ans2,(r[j] + l[j] - 1) * dp[j]);//矩形
                }

        }