单调栈做法76pts求助玄关
查看原帖
单调栈做法76pts求助玄关
669053
Strelizia_楼主2024/10/5 16:31
#include<bits/stdc++.h>
using namespace std;
#define int long long 
int h[1005][1005],r[1005][1005],l[1005][1005];
long long ans;
signed main(){
	int  n,m;
	scanf("%lld %lld",&n,&m);
	char c[1005][1005];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%s",&c[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(c[i][j]=='R') h[i][j]=0;
			else h[i][j]=h[i-1][j]+1;
		}
	}
	for(int i=1;i<=n;i++){
		stack<int>s;
		for(int j=1;j<=m;j++){
			while(!s.empty() and h[i][s.top()]>h[i][j]){
				r[i][s.top()]=j;
				s.pop();
			}
			s.push(j);
		}
		while(!s.empty()){
			r[i][s.top()]=m+1;
			s.pop();
		}
		
		stack<int>s2;
		for(int j=m;j>=1;j--){
			while(!s2.empty() and h[i][s2.top()]>h[i][j]){
				l[i][s2.top()]=j;
				s2.pop();
			}
			s2.push(j);
		}
		while(!s2.empty()){
			l[i][s2.top()]=0;
			s2.pop();
		}
		
		
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
		    ans=max(h[i][j]*(j-l[i][j]),max(ans,h[i][j]*(r[i][j]-j)));
		}
	}
	
	printf("%lld",ans*3);
	return 0;
}
2024/10/5 16:31
加载中...