题解 P3331 【[ZJOI2011]礼物】

· · 题解

这道题……无语

神仙输入方式……希望大家注意一下

那么我们看这道题：

先把问题简化一下：如果这不是一个三维的，只是一个二维的，，那么让你在里面找一个最大正方形，似乎不是很难，全世界都会做。

但是丢到三维上？似乎区别也不是很大啦。

我们仍然把这些当做二维来做，，怎么把它变成二维的，；

很简单，扔掉一维啊，我们先把每一层一片一片的剖开考虑，预处理以某个位置为左上角的最大正方形边长，这个很容易求，可以用单调队列做到O(pqr)O(pqr)。接下来枚举某个左上角，把在每一层上的这个边长全部扣下来，形成一个序列。那么要求的就是最小值乘以选择的长度的最大值。这个东西显然还是可以单调队列求。

那么这样子复杂度就变成了O(pqr)，再分别按照另外两维切片，就可以考虑出所有位置的答案了。

那么完整的思路就是：

枚举某一个方向作为那个 a a 的面，单调地求出对于每一个位置以它为左下角在对应平面上最大的 a a 的大小，然后变换枚举顺序，变成求区间长度乘以区间最小值最大的问题，求出每一个最小值控制的左右端点，相乘取最大值。

程序里有很多注释喔，dalao们加油！ code:

#include<bits/stdc++.h>
using namespace std;
char ch[155][155][155];
int f[155][155][155];
int n[155][155][155];//n数组代表 假设在n【i】【j】【k】 的状态时，在i这一大层上j*k的大小的矩形所能包含的最大的正方形的边长； 
int prefix_s[155][155];//类似于二维前缀和~ 
int L[155],R[155],Q[155],H,T;
int ans;
bool check(int b,int c,int x,int y,int N)//在b*c的矩形中，， 所包含的x*y的小矩形中，检验是否存在边长为 N的合法正方形； 
{
    if(x+N-1>b||y+N-1>c)return false;
    int xx=x+N-1,yy=y+N-1;
    return prefix_s[xx][yy]-prefix_s[xx][y-1]-prefix_s[x-1][yy]+prefix_s[x-1][y-1]==N*N;
}
void solve(int a,int b,int c)
{
    for(register int i=1;i<=a;i++)
    {
        for(register int j=1;j<=b;j++)
            for(register int k=1;k<=c;k++)
                prefix_s[j][k]=f[i][j][k]+prefix_s[j-1][k]+prefix_s[j][k-1]-prefix_s[j-1][k-1];
        for(register int j=1;j<=b;++j)
        {
            int N=0;
            for(register int k=1;k<=c;++k)
            {
                while(check(b,c,j,k,N+1))++N;
                n[i][j][k]=N;
                N-=1;
            }
        }
    }
    //在循环完每个层后，，我们就求解 
    //即：求区间长度乘以区间最小值最大的问题，求出每一个最小值控制的左右端点，相乘取最大值； 
    for(register int j=1;j<=b;j++)
        for(register int k=1;k<=c;k++)
        {
            T=0;
            for(register int i=1;i<=a;i++)
            {
                while(T&&n[Q[T]][j][k]>=n[i][j][k])--T;
                L[i]=Q[T]+1;
                Q[++T]=i;
            }
            T=0;
            for(register int i=a;i>=1;--i)
            {
                while(T&&n[Q[T]][j][k]>=n[i][j][k])--T;
                R[i]=T?Q[T]-1:a;
                Q[++T]=i;
            }
            for(register int i=1;i<=a;++i)
                ans=max(ans,n[i][j][k]*(R[i]-L[i]+1));
        }
}
int main()
{
    int a,b,c;
    scanf("%d%d%d",&b,&a,&c);
    for(register int i=1;i<=a;i++)
        for(register int j=1;j<=b;j++)
            scanf("%s",ch[i][j]+1);//分别以各个层进行寻找，，三个大方向即x，y，z 
    for(register int i=1;i<=a;i++)
        for(register int j=1;j<=b;j++)
            for(register int k=1;k<=c;k++)
                f[i][j][k]=(ch[i][j][k]=='N');
    solve(a,b,c);

    for(register int i=1;i<=b;i++)
        for(register int j=1;j<=a;j++)
            for(register int k=1;k<=c;k++)
                f[i][j][k]=(ch[j][i][k]=='N');
    solve(b,a,c);

    for(register int i=1;i<=c;i++)
        for(register int j=1;j<=b;j++)
            for(register int k=1;k<=a;k++)
                f[i][j][k]=(ch[k][j][i]=='N');
    solve(c,b,a);

    printf("%d",4*ans);
    return 0;
}