首页 > 代码库 > bzojj1764: [Baltic2009]monument
bzojj1764: [Baltic2009]monument
Description
给一个p*q*r的立方体，它由p*q*r个1*1*1的小立方体构成。每个立方体要么被虫蛀，要么不被。现在郑爽要选出一个a*a*b的立方体(方向任意)，使得它没有被虫蛀过，并且4*a*b最大。
Input
第一行是p,q,r <= 150。 以下p*q行，每行r个字符。(x,y,z)这个格子，出现在输入的第1 + (y * p + x - p)行的第z个字符。 N代表未被虫蛀，P代表被虫蛀了。
Output
仅一行，代表郑爽需要的最大的4ab
将悬线扫描法推广至三维，同一层内记录以每个格子为左上角的最大全N正方形的边长a，另外记录以这个正方形边长，向前/后能延伸到的位置（相差b）。
由于方向任意，翻转坐标系计算三次可得到答案。
#include<cstdio>#include<algorithm>int p,q,r,ans=0;bool d[157][157][157];char s[157][157][157];int f[157][157][157],f1[157][157][157],f2[157][157][157],stk[157],stp=0;int min(int a,int b){return a<b?a:b;}void maxs(int&a,int b){if(a<b)a=b;}void calc(){ for(int i=1;i<=p;++i){ for(int j=1;j<=q;++j){ for(int k=1;k<=r;++k){ f[i][j][k]=(s[i][j][k]?1+min(f[i][j-1][k],min(f[i][j-1][k-1],f[i][j][k-1])):0); } } } for(int j=1;j<=q;++j){ for(int k=1;k<=r;++k){ for(int i=1;i<=p;++i){ while(stp&&f[stk[stp]][j][k]>f[i][j][k])f1[stk[stp--]][j][k]=i-1; stk[++stp]=i; } while(stp)f1[stk[stp--]][j][k]=p; for(int i=p;i;--i){ while(stp&&f[stk[stp]][j][k]>f[i][j][k])f2[stk[stp--]][j][k]=i; stk[++stp]=i; } while(stp)f2[stk[stp--]][j][k]=0; } } for(int i=1;i<=p;++i){ for(int j=1;j<=q;++j){ for(int k=1;k<=r;++k){ maxs(ans,f[i][j][k]*(f1[i][j][k]-f2[i][j][k])); } } }}int main(){ scanf("%d%d%d",&q,&p,&r); for(int i=1;i<=p;++i){ for(int j=1;j<=q;++j){ scanf("%s",s[i][j]+1); for(int k=1;k<=r;++k)s[i][j][k]=(s[i][j][k]==‘N‘?1:0); } } calc(); for(int i=1;i<=p;++i){ for(int j=1;j<=q;++j){ for(int k=1;k<=r;++k)if(!d[i][j][k]){ d[i][j][k]=d[j][i][k]=1; std::swap(s[i][j][k],s[j][i][k]); } } } std::swap(p,q); calc(); for(int i=1;i<=p;++i){ for(int j=1;j<=q;++j){ for(int k=1;k<=r;++k)if(d[i][j][k]){ d[i][j][k]=d[k][j][i]=0; std::swap(s[i][j][k],s[k][j][i]); } } } std::swap(p,r); calc(); printf("%d\n",ans*4); return 0;}
bzojj1764: [Baltic2009]monument
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。