Largest Submatrix

给出一个\(n\times m\)的网格，网格里只放有字符a,b,c,d,w,x,,z，现在你可以将其中的w换成a，b，把x换成b，c，把y换成a，c，把z换成a，b，c，询问换完以后最大的子矩阵大小，使其包含一样的字符，\(1 ≤ m, n ≤ 1000\)。

解

注意到字符很少，我们可以钦定最大的子矩阵的字符，也就是尽量把字符变成变成所钦定，正确性显然。

于是接下来问题就变成了如何快速找到这个矩阵了，接下来简要提一下做法，如果初学者看不懂可以看一下这道题目Largest Rectangle in a Histogram，注意到这个类似与最大相同子矩阵的模型，我们只要按行枚举，再枚举列，暴力预处理每一列在以该行为起点上向上所能最长的连续所钦定的字符，预处理出这个问题转化为有m个宽度为1矩形，第i个矩形高度为\(h_i\)，从左至右下端对齐x轴，求其中最大的子矩形。

对于这个问题，按照枚举的思想，先枚举第几个矩形i，以这个矩形为高向左右延伸能最大的矩形，也就是碰到第一个矩形高度小于i的位置，这是单调性问题，考虑单调队列维护，维护一个矩形高度单调递增的单调队列。

于是队列中保存两个值，一个是该矩形向左最远能延伸位置，一个是该矩形的高度，将要入队元素如果能满足单调性，则不予考虑，否则弹出队尾，而队尾元素未被弹出必然是从队尾所对应的位置到当前要入队的位置高度都要比队尾高度大，这也是单调队列的性质，这样队尾所对应矩形最远延伸位置即已经保存下来的最左边位置和入队元素对应位置的上一个，而至于新入队的矩形所对应的最左延升位置即队尾的最左延伸位置，依次维护下去就可以了。

时间复杂度不难得知\(O(nm)\)。

参考代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#define il inline

#define ri register

#define Size 1500

using namespace std;

char A[Size][Size];

bool B[Size][Size];

int n,m,T[Size],R,h[Size],l[Size],ans;

il void work();

template<class free>

il free Max(free,free);

int main(){

    while(scanf("%d%d",&n,&m)!=EOF){ans=0;

        for(int i(1);i<=n;++i)

            scanf("%s",A[i]+1);

        for(int i(1),j;i<=n;++i)

            for(j=1;j<=m;++j)

                if(A[i][j]=='a'||A[i][j]=='w'||A[i][j]=='y'||A[i][j]=='z')B[i][j]|=true;

        work(),memset(B,0,sizeof(B));

        for(int i(1),j;i<=n;++i)

            for(j=1;j<=m;++j)

                if(A[i][j]=='b'||A[i][j]=='w'||A[i][j]=='x'||A[i][j]=='z')B[i][j]|=true;

        work(),memset(B,0,sizeof(B));

        for(int i(1),j;i<=n;++i)

            for(j=1;j<=m;++j)

                if(A[i][j]=='c'||A[i][j]=='x'||A[i][j]=='y'||A[i][j]=='z')B[i][j]|=true;

        work(),memset(B,0,sizeof(B)),printf("%d\n",ans);

    }

    return 0;

}

il void work(){

    for(int i(1),j;i<=n;++i){

        for(j=1;j<=m;++j){

            h[j]=0,l[j]=j;while(B[i+h[j]][j])++h[j];

            while(0<R&&h[T[R]]>h[j])

                ans=Max((j-l[T[R]])*h[T[R]],ans),l[j]=l[T[R]],--R;

            T[++R]=j;

        }while(0<R)ans=Max((j-l[T[R]])*h[T[R]],ans),--R;

    }

}

template<class free>

il free Max(free a,free b){

    return a>b?a:b;

}

巴特西

Largest Submatrix

解

最新文章

热门文章