题解：P10965 Largest Submatrix

ycy1124 · 2024-09-30 18:00:11 · 题解

题意

有一个 n \times m 的字符矩阵，所有的字符都可以转化为 \tt a,b,c 这三种字符的任意两种或三种，求转换后所有元素全部相同的子矩阵的最大大小。

思路

不难看出，这题其实就是把 P4147 玉蟾宫跑三遍。

其实这题就是单调栈求最大子矩阵的板子题。

由于 \tt x,y,z,w 都可以变成至少 \tt a,b,c 其中的两个，所以不难知道，将所有的 \tt x,y,z,w 都变成 \tt a,b,c 的答案一定不会更劣。

我们可以先对于每一个位置，求出从这个位置往下延伸，分别能得到多少个连续的 \tt a,b,c，用 h_{i,j} 来表示。

这样分别得到三个矩阵后，我们就可以考虑分别求出所有元素是 \tt a,b,c 的最大子矩阵了。

首先了解一下单调栈的定义：单调栈就是指栈内所有元素都是单调递增或单调递减的。例如 1 2 5 10 100 1000 就是一个单调递增的数列。（单调递增与单调不降是有区别的，注意区分）

对于单调栈求最大子矩阵，我们用的是单调递增的栈。我们对于每一行遍历一遍 j，然后对于每个 h_{i,j}，重复执行这个操作直到栈中没有大于等于它的元素：首先弹出栈顶，将栈顶的宽度累加到 js 上，然后更新一遍答案为栈顶的高度 \times js，当所有大于等于 h_{i,j} 的弹完了以后，将 h_{i,j} 与 js+1 一起压入栈中。代码如下：

int js=0;
while(!q.empty()&&h[i][j]<=q.top().h){
    ans=max(ans,q.top().h*(js+q.top().w));
    js+=q.top().w;
    q.pop();
}
q.push({h[i][j],1+js});

这段代码实现的是：对于栈中的每一个高度，假如当前压入栈中的高度比它低，那么以它为高的最大矩形是一定无法继续向后延伸的，于是就可以将它弹出，计算一遍以它为高的矩阵大小，然而进去的小的高度的矩形是可以向高的下面延伸的，所以宽度要增加上以高的高度为高的矩形的宽度，也就是累加的 js。

最后跑三遍单调栈分别求出全为 \tt a,b,c 的子矩阵的最大大小，取个 max 输出就行了。

代码

#include<bits/stdc++.h>
using namespace std;
char a[1001][1001];
int h1[1001][1001];
int h2[1001][1001];
int h3[1001][1001];
struct Node{
    int h,w;
};
stack<Node>q;
int ans=0;
int main(){
    int n,m;
    while(cin>>n>>m){
        ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                h1[i][j]=h2[i][j]=h3[i][j]=0;
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=n;i++){//统计往下延伸的数组
            for(int j=1;j<=m;j++){
                if(h1[i][j]==0&&a[i][j]!='x'&&a[i][j]!='b'&&a[i][j]!='c'){
                    int js=0;
                    int x=i;
                    int y=j;
                    while(a[x][y]!='x'&&x>=1&&a[x][y]!='b'&&a[x][y]!='c'){
                        h1[x][y]=++js;
                        x--;
                    }
                }
            } 
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(h2[i][j]==0&&a[i][j]!='y'&&a[i][j]!='a'&&a[i][j]!='c'){
                    int js=0;
                    int x=i;
                    int y=j;
                    while(a[x][y]!='y'&&x>=1&&a[x][y]!='a'&&a[x][y]!='c'){
                        h2[x][y]=++js;
                        x--;
                    }
                }
            } 
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(h3[i][j]==0&&a[i][j]!='w'&&a[i][j]!='b'&&a[i][j]!='a'){
                    int js=0;
                    int x=i;
                    int y=j;
                    while(a[x][y]!='w'&&x>=1&&a[x][y]!='b'&&a[x][y]!='a'){
                        h3[x][y]=++js;
                        x--;
                    }
                }
            } 
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(q.empty()||h1[i][j]>q.top().h){//跑单调栈
                    q.push({h1[i][j],1});
                }
                else{
                    int js=0;
                    while(!q.empty()&&h1[i][j]<=q.top().h){
                        ans=max(ans,q.top().h*(js+q.top().w));
                        js+=q.top().w;
                        q.pop();
                    }
                    q.push({h1[i][j],1+js});
                }
            }
            int js=0;
            while(!q.empty()){
                ans=max(ans,q.top().h*(js+q.top().w));
                js+=q.top().w;
                q.pop();
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(q.empty()||h2[i][j]>q.top().h){
                    q.push({h2[i][j],1});
                }
                else{
                    int js=0;
                    while(!q.empty()&&h2[i][j]<=q.top().h){
                        ans=max(ans,q.top().h*(js+q.top().w));
                        js+=q.top().w;
                        q.pop();
                    }
                    q.push({h2[i][j],1+js});
                }
            }
            int js=0;
            while(!q.empty()){
                ans=max(ans,q.top().h*(js+q.top().w));
                js+=q.top().w;
                q.pop();
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(q.empty()||h3[i][j]>q.top().h){
                    q.push({h3[i][j],1});
                }
                else{
                    int js=0;
                    while(!q.empty()&&h3[i][j]<=q.top().h){
                        ans=max(ans,q.top().h*(js+q.top().w));
                        js+=q.top().w;
                        q.pop();
                    }
                    q.push({h3[i][j],1+js});
                }
            }
            int js=0;
            while(!q.empty()){
                ans=max(ans,q.top().h*(js+q.top().w));
                js+=q.top().w;
                q.pop();
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

AC 记录。