POJ 1964 City Game【単調スタック01マトリックス中の最大の1矩形】

City Game
Time Limit: 3000 MS
 
メモリLimit: 30000 K
Total Submissions: 6090
 
Acceepted: 2439
Description
Bob is a strategy game programming specialist.In his new city building game the gaming environment is as follows:a city is built up by aras、in which there strets、trees、factores and buildings.The e e is still some space in the ara that is unoccupied.The strate gic task of his game is to win much the free spaces.To win rent money mut muterect buildings,atcacturas long and wide as you can.Bob is trying to find a way to build the biggest possible ble building in each ara.But hecos acros some probles–he is not allowed to destrory already existing buildings,trees.strees.strees.orts  Each ara has its width and length.The ara is divided into a grid of equal square units.The rent paid for each unit on which you're building stands 3$  Your task is to help Bob solive this problem.The whole city is divided into K aras.Each one of the aras is rectanglar and has a different gride size wingth M and width N.The exis the the spingmartunkers
Input
The first line of the input contains an integer K–determining the number of datasets.Next line s contain the ara descriptions.One defined in the following way:The first line contains tgerse 1000separated by blank space.The next M lineas contain N smbors that mark the reerved or free grid units、separated by a blank space.The smbors used are:  R-reerved unit  F–free unit  In the end of each ara description there is a separating line.
Output
For each data set in the input print on a separate line,on the standard output,the integer that represents the profit otained by erecting the largest building in the are encoded by the data set.
Sample Input

2
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F

5 5
R R R R R
R R R R R
R R R R R
R R R R R
R R R R R

Sample Output

45
0

ソurce
Southeastern Europe 2004
題意と考え方
この問題はPOJ 3494 Largest Submatix of All 1’sの「単調スタック01行列の中で最大の1矩形」と同じで、「F」は1を表し、「R」は0を表し、入力フォーマットは小さい変動があります.
C++プログラム

#include
#include

using namespace std;

const int N=1005;

int a[N][N];
int l[N],s[N];

int main()
{
	int n,m,k;
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d%d",&m,&n);
		memset(a,0,sizeof(a));
		//   
		for(int i=1;i<=m;i++)
		  for(int j=1;j<=n;j++)
		  {
		  	char c;
		  	scanf(" %c",&c);
		  	a[i][j]=(c=='F');//   'F'   1 
		  }
		//    
		for(int i=1;i<=n;i++)
		  for(int j=m;j>=1;j--)
		  	if(a[j][i]) a[j][i]+=a[j+1][i];
		
		int ans=0;
		for(int i=1;i<=m;i++)//   i  
		{
			a[i][n+1]=-1;
			int top=0;
			//        
			for(int j=1;j<=n+1;j++)
			{
				l[j]=j;
				while(top>0&&a[i][s[top]]>a[i][j])
				{
					ans=max(ans,a[i][s[top]]*(j-l[s[top]]));
					l[j]=l[s[top]];
					top--;
				}
				if(top>0&&a[i][s[top]]==a[i][j]) l[j]=l[s[top]];
				s[++top]=j;
			}
		}
		printf("%d
",3*ans);
	}
	return 0;
}