这个东西 搞法不一 我是这么搞的 沿着 z 轴的方向看 一定是一些重叠的正方形叠在一起 我们对于每一个z 都对 (x,y) 求出 fx,y 表示最大的以 (x,y) 为右下角的正方形的大小 然后在 z 这一维上 大小就是区间最小值 我们用单调栈弄一弄就好了 我写的二分求fx,y 复杂度 O(n3logn) 但是实际上用悬线法可以做到 O(n3)
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } inline void read(char *s){ char c=nc(); int len=0; for (;!(c>='A' && c<='Z');c=nc()); for (;c>='A' && c<='Z';s[++len]=c,c=nc()); s[++len]=0; } const int N=155; int _g[3][N][N][N]; int h[N],l[N],r[N]; int sta[N],p; inline int calc(int n){ h[0]=h[n+1]=-1; p=0; sta[++p]=0; for (int i=1;i<=n;i++){ while (p && h[i]<=h[sta[p]]) p--; l[i]=i-sta[p]; sta[++p]=i; } p=0; sta[p]=n+1; for (int i=n;i;i--){ while (p && h[i]<=h[sta[p]]) p--; r[i]=sta[p]-i; sta[++p]=i; } int ret=0; for (int i=1;i<=n;i++) ret=max(ret,h[i]*(l[i]+r[i]-1)); return ret; } int f[N][N][N]; int g[N][N][N]; inline int sum(int x1,int y1,int x2,int y2,int k){ return g[k][x2][y2]+g[k][x1-1][y1-1]-g[k][x2][y1-1]-g[k][x1-1][y2]; } inline int Solve(int p,int q,int r){ for (int k=1;k<=r;k++) for (int i=1;i<=p;i++) for (int j=1;j<=q;j++) g[k][i][j]+=g[k][i][j-1]; for (int k=1;k<=r;k++) for (int i=1;i<=p;i++) for (int j=1;j<=q;j++) g[k][i][j]+=g[k][i-1][j]; for (int k=1;k<=r;k++) for (int i=1;i<=p;i++) for (int j=1;j<=q;j++){ int L=0,R=min(i,j)+1,x; while (L+1<R){ x=(L+R)>>1; if (!sum(i-x+1,j-x+1,i,j,k)) L=x; else R=x; } f[k][i][j]=L; } int ret=0; for (int i=1;i<=p;i++) for (int j=1;j<=q;j++){ for (int k=1;k<=r;k++) h[k]=f[k][i][j]; ret=max(ret,calc(r)); } return ret; } int main(){ int p,q,r; char str[N]; freopen("monument.in","r",stdin); freopen("monument.out","w",stdout); read(q); read(p); read(r); for (int i=1;i<=p;i++) for (int j=1;j<=q;j++){ read(str); for (int k=1;k<=r;k++) _g[0][k][i][j]=_g[1][j][i][k]=_g[2][i][j][k]=str[k]=='P'; } int Ans=0; memcpy(g,_g[0],sizeof(g)); Ans=max(Ans,Solve(p,q,r)); memcpy(g,_g[1],sizeof(g)); Ans=max(Ans,Solve(p,r,q)); memcpy(g,_g[2],sizeof(g)); Ans=max(Ans,Solve(q,r,p)); printf("%d\n",Ans*4); return 0; }