poj1964 City Game---单调栈

题目链接：https://vjudge.net/problem/POJ-1964

题意：一个矩阵有R和F两种字母，求最大全F子矩阵

n,m<=1000的数据范围要求一个O(nm)的算法。首先处理出每个点能向上延伸的长度h[i][j]，然后正解只要想到如下方法：对每一行，用poj2559单调栈的方法求最大面积即可

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;

const int N=1000+10;
int t,i,j,k,m,n,h[N][N],l[N],r[N];
char ch[N][N];

int main(){
	std::ios::sync_with_stdio(false);
	cin>>t;
	while (t--){
	  memset(r,0,sizeof(r));
	  memset(l,0,sizeof(l));
	  memset(h,0,sizeof(h));
	  cin>>m>>n;
      for (i=1;i<=m;i++)
	    for (j=1;j<=n;j++)
	      cin>>ch[i][j]; 
	  for (i=1;i<=m;i++)
	    for (j=1;j<=n;j++)
	      h[i][j]=(ch[i][j]=='F')?h[i-1][j]+1:0;
	  int ans=0;
	  for (k=1;k<=m;k++){
	  	stack<int> st;
	  	h[k][0]=1e7; h[k][n+1]=-1; st.push(0);	  	
		for (i=1;i<=n+1;i++){
		  while (!st.empty()&&h[k][i]<h[k][st.top()]){
		  	r[st.top()]=i; st.pop();
		  }
		  st.push(i);
		}
		h[k][n+1]=1e7; h[k][0]=-1; 
		while (!st.empty()) st.pop(); st.push(n+1);
		for (i=n;i>=0;i--){
		  while (!st.empty()&&h[k][i]<h[k][st.top()]){
		  	l[st.top()]=i; st.pop();
		  }
		  st.push(i);
		}
		for (i=1;i<=n;i++) ans=max(ans,h[k][i]*(r[i]-l[i]-1));
	  }
	  cout<<ans*3<<endl;
	}
	return 0;
}