首页 > 代码库 > 3039: 玉蟾宫
3039: 玉蟾宫
3039: 玉蟾宫
Time Limit: 2 Sec Memory Limit: 128 MBSubmit: 512 Solved: 311
[Submit][Status]
Description
有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
这片土地被分成N*M个格子，每个格子里写着‘R‘或者‘F‘，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着‘F‘并且面积最大。
但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为S，它们每人给你S两银子。
Input
第一行两个整数N,M，表示矩形土地有N行M列。
接下来N行，每行M个用空格隔开的字符‘F‘或‘R‘，描述了矩形土地。
Output
输出一个整数，表示你能得到多少银子，即(3*最大‘F‘矩形土地面积)的值。
Sample Input
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
Sample Output
HINT
对于50%的数据，1<=N,M<=200
对于100%的数据，1<=N,M<=1000
Source
Poetize4
题解：这个，是我这辈子第一次成功的写最大子矩阵问题呵呵呵（phile：这这这。。。 HansBug：我是蒟蒻求不鄙视TT）。仔细说下子——首先通过二重循环递推出各个F点的左边，右边，下边各有多少个F（均算自己在内），然后开工——枚举每一个点，当为1的时候凉拌，为0的时候开始向下“挂线”（这正是网上所说的悬线法）——假如这个点正下方为0，则当啥都没做（本程序里面还是执行了下内循环，虽然次数为0。。= =）；假如刚好是个1，那就顺藤摸瓜一直往下，每往下一格便记录下这根线当前左侧最窄值为多少，右侧最窄值为多少，然后当已经挂到长度为K时，则当前最新面积为K*(左侧最窄值+右侧最窄值-1)（PS：记得减1），然后每次max一下，结果就出来啦（特特特特特特特别提醒：记得乘3！！！！）
1 var 2 i,j,k,l,m,n,ans,a1,a2:longint; 3 a,lef,rig,dow:array[0..1100,0..1100] of longint; 4 c1:char; 5 function min(x,y:longint):longint;inline; 6 begin 7 if x<y then min:=x else min:=y; 8 end; 9 function max(x,y:longint):longint;inline;10 begin11 if x>y then max:=x else max:=y;12 end;13 begin14 readln(n,m);15 for i:=1 to n do16 begin17 a[i,0]:=0;18 while not(eoln) do19 begin20 read(c1);c1:=upcase(c1);21 if (c1<>‘F‘) and (c1<>‘R‘) then continue;22 inc(a[i,0]);23 if c1=‘F‘ then a[i,a[i,0]]:=1 else a[i,a[i,0]]:=0;24 end;25 readln;26 a[i,0]:=0;27 end;28 for i:=1 to n do29 for j:=1 to m do30 if a[i,j]=1 then lef[i,j]:=lef[i,j-1]+1 else lef[i,j]:=0;31 for i:=n downto 1 do32 for j:=m downto 1 do33 begin34 if a[i,j]=1 then rig[i,j]:=rig[i,j+1]+1 else rig[i,j]:=0;35 if a[i,j]=1 then dow[i,j]:=dow[i+1,j]+1 else dow[i,j]:=0;36 end;37 ans:=0;38 for i:=0 to n do39 for j:=1 to m do40 if a[i,j]=0 then41 begin42 a1:=-1;43 a2:=-1;44 for k:=1 to dow[i+1,j] do45 begin46 if a1=-1 then a1:=lef[i+k,j] else a1:=min(a1,lef[i+k,j]);47 if a2=-1 then a2:=rig[i+k,j] else a2:=min(a2,rig[i+k,j]);48 ans:=max(ans,(a1+a2-1)*k);49 end;50 if a1=-1 then continue;51 end;52 writeln(ans*3);53 end.
3039: 玉蟾宫