「某讲稿」极大化思想与最大子矩阵的探究学习笔记

写在前面

这应该算是 $author$ 的第一篇知识笔记吧 $qwq$

题目引入

先来康康一道题吧，

「Luogu P1578」奶牛浴场

题目描述

由于 $John$ 建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，$John$ 决定在牛场中建造一个大型浴场。但是 $John$ 的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，$John$ 希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于 $Clevow$ 了。你还能帮助 $Clevow$ 吗？

$John$ 的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。

$Clevow$ 当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。

输入输出格式

输入格式：

输入文件的第一行包含两个整数 $L$ 和 $W$，分别表示牛场的长和宽。文件的第二行包含一个整数 $n$，表示产奶点的数量。以下n行每行包含两个整数 $x$ 和 $y$，表示一个产奶点的坐标。所有产奶点都位于牛场内，即：$0\le x\le L$，$0\le y\le W$。

输出格式：

输出文件仅一行，包含一个整数 $S$，表示浴场的最大面积。

输入输出样例

输入样例 #1：

输出样例 #1：

80
/这行是为了前面有标号

说明

$0\le n\le 5000$

$1\le L,W\le 30000$

$Winter\ Camp\ 2002$

又比如，这道题：

「Luogu P1169」 [ZJOI2007]棋盘制作

题目描述

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

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

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

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

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

输入输出格式

输入格式：

包含两个整数 $N$ 和 $M$ ，分别表示矩形纸片的长和宽。接下来的$N$行包含一个 $N \times M$ 的 $01$ 矩阵，表示这张矩形纸片的颜色（ $0$ 表示白色，$1$ 表示黑色）。

输出格式：

包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。

输入输出样例

输入样例 #1：

输出样例 #1：

4
6

说明

对于 $20\%$ 的数据，$N, M \le 80$

对于 $40\%$ 的数据，$N, M ≤ 400$

对于 $100\%$ 的数据，$N, M ≤ 2000$

正文

求解矩阵中最大子矩阵问题，可以用极大化思想

先来看一些定义：

有效子矩形：顾名思义，即满足条件的矩形

极大子矩形：原矩阵中无法再拓展（即向四周都无法拓展）的子矩形

最大子矩形：~~字面意思~~，我们要求的答案

极大化思想

可以证明，最大子矩形一定是极大子矩形

于是，我们就可设计一个算法，即枚举所有极大子矩阵，然后求解

但是~~暴力出奇迹~~暴力总不是最好的解法，我们可以高效利用我们处理出来的信息，将算法的复杂度降到$O(n^2)$

不同的题型，不同的解法

对于给出的第一道题，肯定不能基于矩形的大小做，于是就可以设计一个基于障碍点数的算法

由于极大化思想，一个极大子矩阵的边缘上一定有障碍点，所以可以枚举每个障碍点，再从障碍点扩展

这叫也不知道叫什么的算法

如图：

这是一个矩阵，为了方便处理，我们引入了矩阵的四个顶点

然后枚举每个点，比如我们做到这点，只向一个方向更新，令 $U$ 为以 $i$ 点为左边的矩形最大可能的上界编号，$D$ 则为相对应的最大可能的下界编号

此时：$U=7\ \ D=0$

可以看出，还可以向右拓展，于是做到 $j$ 点

此时：$U=7\ \ D=0$

虽然说，现在的答案已经是最大了（程序又不是人，但是我们还要拓展

既然要求 $i$ 点一定要在矩形的边缘上且矩形内不能有障碍点，所以就改变 $U$ 或 $D$ 的值

此时：$U=7\ \ D=3$

然后继续往右拓展，直到 $U==D$ 或者所有点都拓展完，前者不能拓展的原因是因为无法形成矩形——已经是一条线了

然后将 $i$ 点右移，继续做，不断更新答案

但是，这样就足够了嘛？

样例过了啊，~~样例是真水~~

我们在样例的基础上加两个点

是不是就忘记了这两种情况，而实际上，这两种情况就都是要竖着做一遍，但是由于嫌烦

还是特判一下好了，前者排序后特判，后者再从右往左扫一遍（一开始我们是从右往左更新

Code：

#include<bits/stdc++.h>
#define M b[i].y
#define N 5007//由于坐标系和文中所描述的方法对x和y的定义有点不同
using namespace std;//造成的小差异读者可以自行思考
struct node{
    int x,y;
    node(int a,int b):x(a),y(b){}
    node(){}
}b[N];
int n,m,t,ans,D,U;
inline int read() {
    int s=0;
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline bool cmp(node a,node b) {return a.y<b.y;}
inline bool Cmp(node a,node b) {return a.x<b.x;}
int main()
{
    int i,j;
    n=read(),m=read(),t=read();
    for(i=1;i<=t;++i) b[i].x=read(),b[i].y=read();
    b[++t]=node(0,m),b[++t]=node(n,0),
    b[++t]=node(0,0),b[++t]=node(n,m);
    sort(b+1,b+1+t,cmp);//按y排序
    for(i=1;i<t;++i) ans=max(ans,(b[i+1].y-b[i].y)*n);//对于第一种情况的特判
    sort(b+1,b+1+t,Cmp);
    for(i=2;i<t;++i) {
        D=0,U=m;
        for(j=i+1;j<=t;++j) {
            ans=max(ans,(b[j].x-b[i].x)*(U-D));
            if(D<=b[j].y&&b[j].y<=U) {
            if(b[j].y==M) break;
            if(M<b[j].y&&b[j].y<U) U=b[j].y;
            if(D<b[j].y&&b[j].y<M) D=b[j].y;
            }
        }
        D=0,U=m;
        for(j=i-1;j;--j) {
            ans=max(ans,(b[i].x-b[j].x)*(U-D));
            if(D<=b[j].y&&b[j].y<=U) {
            if(b[j].y==M) break;
            if(M<b[j].y&&b[j].y<U) U=b[j].y;
            if(D<b[j].y&&b[j].y<M) D=b[j].y;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

悬线法

当障碍点变得密集，上文所述的方法就不适用了，于是就引出了新算法——悬线法

这是一个基于矩阵大小的算法

对于每个点处理：

l[i][j]：以(i,j)点为下界的半极大有效子矩形(因为可能还能向下拓展)的左边界(障碍点的j值)
r[i][j]：以(i,j)点为下界的半极大有效子矩形的右边界
h[i][j]：以(i,j)点为下界的半极大有效子矩形的高，上界到下界的距离

递推式：

$(i,j)$ 位置左右最近的障碍点可以用一次 $DP$ 处理

for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)//一开始l[i][j]和r[i][j]都是j
        b[i][j]=read(),l[i][j]=r[i][j]=j;
for(i=1;i<=n;i++) {
    for(j=2;j<=m;j++)
        if(b[i][j]^b[i][j-1])
            l[i][j]=l[i][j-1];
    for(j=m-1;j;j--)
        if(b[i][j]^b[i][j+1])
            r[i][j]=r[i][j+1];
    }

然后在每个点更新答案

Code：

#include<bits/stdc++.h>
#define rgt register
#define N 2007
using namespace std;
int n,m,l[N][N],r[N][N],h[N][N],L,a,res,ans;
bool b[N][N];
inline bool read() {
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    return c-'0';
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            b[i][j]=read(),l[i][j]=r[i][j]=j;
    for(i=1;i<=n;i++) {
        for(j=2;j<=m;j++)
            if(b[i][j]^b[i][j-1])//稍微变换一下，和左右同色的就是障碍点
                l[i][j]=l[i][j-1];
        for(j=m-1;j;j--)
            if(b[i][j]^b[i][j+1])
                r[i][j]=r[i][j+1];
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=m;j++) {
            if(i>1&&b[i][j]^b[i-1][j]) {
                l[i][j]=max(l[i][j],l[i-1][j]);
                r[i][j]=min(r[i][j],r[i-1][j]);
                h[i][j]=h[i-1][j]+1;
            }
            else h[i][j]=1;
            L=r[i][j]-l[i][j]+1,a=min(L,h[i][j]);
            res=max(res,a*a);
            ans=max(ans,L*h[i][j]);
        }
    }
    printf("%d\n%d",res,ans);
    return 0;
}

「某讲稿」极大化思想与最大子矩阵的探究学习笔记

写在前面

题目引入

「Luogu P1578」奶牛浴场

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例 #1：

输出样例 #1：

说明

「Luogu P1169」 [ZJOI2007]棋盘制作

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例 #1：

输出样例 #1：

说明

正文

极大化思想

不同的题型，不同的解法

Code：

悬线法

Code：

推荐题目

「SP6517」JOCHEF - Farmer Sepp 解题报告

「Luogu P4802」[CCO 2015]路短最解题报告

h^ovny

写在前面

题目引入

「Luogu P1578」 奶牛浴场

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例 #1：

输出样例 #1：

说明

「Luogu P1169」 [ZJOI2007]棋盘制作

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例 #1：

输出样例 #1：

说明

正文

极大化思想

不同的题型，不同的解法

Code：

悬线法

Code：

推荐题目

「SP6517」JOCHEF - Farmer Sepp 解题报告

「Luogu P4802」[CCO 2015]路短最 解题报告

h^ovny

「Luogu P1578」奶牛浴场

「Luogu P4802」[CCO 2015]路短最解题报告