【题意】
给定一个'R''F'矩阵,求最大全部由'F'组成的矩形面积
【输入】
第一行k,表示k组数据
每组数据第一行n、m
接下来描述一个n*m的矩阵
【输出】
对于每组数据,输出最大面积
单调栈
首先预处理一下,求出每个(i,j)包括自己向下有几个连续的F
然后枚举行数,问题就简化回一维求立方图最大面积了
program poj1964; var tot,ans,k,n,m,i,j:longint; f,map:array [0..1001,0..1001] of longint; dl:array [0..1001] of longint; temp:char; function min (a,b:longint):longint;inline; begin if a<b then exit(a) else exit(b); end; begin readln(k); while k>0 do begin dec(k); readln(n,m); for i:=1 to n do begin for j:=1 to m do begin repeat read(temp); until (temp='R')or(temp='F'); if temp='R' then map[i,j]:=0 else map[i,j]:=1; end; readln; end; ans:=0; fillchar(f,sizeof(f),0); for i:=n downto 1 do for j:=m downto 1 do if map[i,j]=1 then f[i,j]:=f[i+1,j]+1; for i:=1 to n do begin tot:=0; for j:=1 to m+1 do begin while (tot>0)and(f[i,j]<f[i,dl[tot]]) do begin if ans<f[i,dl[tot]]*(j-1-dl[tot-1]) then ans:=f[i,dl[tot]]*(j-1-dl[tot-1]); dec(tot); end; inc(tot); dl[tot]:=j; end; end; writeln(3*ans); end; end.