CH1803 City Game

题意

这片土地被分成NM个格子，每个格子里写着'R'或者'F'，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。

现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着'F'并且面积最大。

但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为S，它们每人给你3S两银子。

1<=N,M<=1000

分析

最大01子矩阵，单调栈解决。我还是第一次看到正规写法的单调栈，原来还要记录长度。

比较通用的技巧是使用0来清空栈已达到统计完全的目的。

时间复杂度\(O(NM)\)

代码

话说没人给3S银子不就9S了吗？

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

	rg T data=0,w=1;

	rg char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') w=-1;

		ch=getchar();

	}

	while(isdigit(ch))

		data=data*10+ch-'0',ch=getchar();

	return data*w;

}

template<class T>il T read(rg T&x){

	return x=read<T>();

}

typedef long long ll;

co int N=1e3+1;

int a[N][N],b[N];

int s[N],w[N],p;

int main(){

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

	int n=read<int>(),m=read<int>();

	char buf[2];

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

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

			scanf("%s",buf);

			a[i][j]=buf[0]=='F';

		}

	int ans=0;

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

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

			b[j]=a[i][j]?b[j]+1:0;

		p=0;

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

			if(b[j]>s[p]) s[++p]=b[j],w[p]=1;

			else{

				int width=0;

				while(s[p]>b[j]){

					width+=w[p];

					ans=std::max(ans,width*s[p]);

					--p;

				}

				s[++p]=b[j],w[p]=width+1;

			}

		}

	}

	printf("%d\n",3*ans);

	return 0;

}