学步园

题目大意：给你一个N行M列的地，每块地上有R或F，求这个图中最大的由F构成的矩形面积 n,m<=1000

这道题，如果给定你矩形的下底所在的行，那么我们就用一个单调栈维护，即可，然后枚举矩形的下底所在的行 O(n^2)

#include<cstdio>
#include<cstring>
const int maxn=1010; 
using namespace std;

inline int max(int a,int b){
	return a>b?a:b;
}

int n,m;
int s[maxn];
int h[maxn][maxn];
int len[maxn];
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)	
		for (int j=1;j<=m;++j){
			char tmp=1;
			while (!(tmp=='F' || tmp=='R'))
				tmp=getchar();
			if (tmp=='F')
				h[i][j]=h[i-1][j]+1;
		}
	int ans=0;
	for (int i=1;i<=n;++i){
		memset(len,0,sizeof(len));
		int tot(0);
		for (int j=1;j<=m;++j){
			if (!tot || h[i][j]>=h[i][s[tot]]){
				s[++tot]=j;
				len[j]=1;
				continue;
			}
			len[j]=0;
			for (;h[i][j]<h[i][s[tot]];--tot)
				len[j]+=len[s[tot]],ans=max(ans,h[i][s[tot]]*len[j]);
			len[j]++;
			s[++tot]=j;
		}
		int xx=0;
		for (;tot;--tot)
			xx+=len[s[tot]],ans=max(ans,h[i][s[tot]]*xx);
	}
	printf("%d\n",ans*3);
	return 0;
}