礼物(gift)
【题目描述】
小白的生日就要到了，小蓝决定送一件自己亲手做的手工艺品使自己的礼
物与众不同。具体来说，小蓝已经通过某种方式制作出了一个p×q×r 的木块（由
pqr 个单位小木块组成）。但由于小蓝手艺不精，现在这个木块中的有些单位小
木块是有问题的(有裂缝、里面是空心等等)，这样的礼物小蓝是不可能直接送出
去的。
于是小蓝决定在这个木块中再挖出一个a×a×b 的子木块(即要求挖出的长
方体木块存在两条长度相等的相邻边)，当然这个子木块中是不能包含有问题的
单位小木块的。为了使这个木块上能包含更多的图案，小蓝希望从所有可行的方
案中挑取4ab 的值最大的方案。但小蓝光检测木块中哪些地方有问题就已经耗尽
了体力，作为小蓝的好友，你能帮帮小蓝吗？
【输入说明】
每个输入文件中仅包含一个测试数据。
第一行包含三个由空格隔开的正整数，p,q,r。
接下来有pq 行，每行包含r 个字符，每个字符只可能是’P’(Poor)或者’
N’(Nice)，表示该单位小木块有问题或者没问题。具体的说，第1+(yp+x-p)行
的第z 个字符描述的是坐标为(x,y,z) 的小木块情况。
(1<=x<=p,1<=y<=q,1<=z<=r)
【输出说明】
输出文件仅包含一个整数，表示最佳方案的4ab 的值。
【样例输入】
3 2 5
PNNNN
PNNNN
NPPNP
PNNNP
NNNNP
PPNNP
【样例输出】
24
【数据范围】
对于100%的数据，0<p,q,r<=150，输入中至少包含一个’N’
pqr=3375000，即使是2s的时限，再乘以一个log也会超时
所以肯定存在线性算法
唯一特殊的地方就是子方块是a*a*b的
既然是a*a，就有些不同了，
假设枚举z坐标，那么可以用线性时间内求出(x,y,z)在平面z内向一个方向延伸能构成的最大正方形边长
这样问题就从三维转化到了二维，等价于求一些直方柱的最大矩形，例如poj2559
这个问题可以利用单调栈在线性时间内解决，只要枚举x、y，将这一列当做直方柱来计算最大面积即可
因为这个a*a*b的字块方向不确定，所以要在三个方向都搞一搞
program gift;
var
w,tot,mid,s,e,o,ans,p,q,r,i,j,k:longint;
map:array [0..151,0..151,0..151] of char;
dl,point:array [0..151] of longint;
f:array [0..151,0..151,0..151] of longint;
function min (a,b:longint):longint;inline;
begin
if a<b then exit(a)
else exit(b);
end;
begin
assign(input,'gift.in');
reset(input);
assign(output,'gift.out');
rewrite(output);
readln(p,q,r);
for j:=1 to q do
for i:=1 to p do
begin
for k:=1 to r do
read(map[i,j,k]);
readln;
end;
ans:=1;
fillchar(f,sizeof(f),0);
for i:=p downto 1 do
for j:=q downto 1 do
for k:=1 to r do
if map[i,j,k]='P' then f[i,j,k]:=0
else f[i,j,k]:=min(min(f[i+1,j,k],f[i,j+1,k]),f[i+1,j+1,k])+1;
for i:=1 to p do
for j:=1 to q do
begin
tot:=0;
for k:=1 to r+1 do
begin
while (tot>0)and(f[i,j,k]<f[i,j,dl[tot]]) do
begin
if ans<f[i,j,dl[tot]]*(k-dl[tot-1]-1) then
ans:=f[i,j,dl[tot]]*(k-dl[tot-1]-1);
dec(tot);
end;
inc(tot);
dl[tot]:=k;
end;
end;
fillchar(f,sizeof(f),0);
for i:=p downto 1 do
for k:=r downto 1 do
for j:=1 to q do
if map[i,j,k]='P' then f[i,j,k]:=0
else f[i,j,k]:=min(min(f[i+1,j,k],f[i,j,k+1]),f[i+1,j,k+1])+1;
for i:=1 to p do
for k:=1 to r do
begin
tot:=0;
for j:=1 to q+1 do
begin
while (tot>0)and(f[i,j,k]<f[i,dl[tot],k]) do
begin
if ans<f[i,dl[tot],k]*(j-dl[tot-1]-1) then
ans:=f[i,dl[tot],k]*(j-dl[tot-1]-1);
dec(tot);
end;
inc(tot);
dl[tot]:=j;
end;
end;
fillchar(f,sizeof(f),0);
for j:=q downto 1 do
for k:=r downto 1 do
for i:=1 to p do
if map[i,j,k]='P' then f[i,j,k]:=0
else f[i,j,k]:=min(min(f[i,j+1,k],f[i,j,k+1]),f[i,j+1,k+1])+1;
for j:=1 to q do
for k:=1 to r do
begin
tot:=0;
for i:=1 to p+1 do
begin
while (tot>0)and(f[i,j,k]<f[dl[tot],j,k]) do
begin
if ans<f[dl[tot],j,k]*(i-dl[tot-1]-1) then
ans:=f[dl[tot],j,k]*(i-dl[tot-1]-1);
dec(tot);
end;
inc(tot);
dl[tot]:=i;
end;
end;
writeln(ans*4);
close(input);
close(output);
end.