自动搬运

查看原文

来自洛谷，原作者为

	ycy1124 ENTJ-A | 有事私。| 清关了，私信基本也不会回关（除非满足条件），但可以支持小号回关 | 出去玩去了。不在线。微信可能上。

搬运于2025-08-24 23:02:59，当前版本为作者最后更新于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 记录。