据说联赛之前写题解可以涨RP
这题的输入格式半天没看懂…其实是有q层摞在一起,每一层大小都是p*r,依次输入q层的情况。那么首先我们枚举三种挖方块的姿势,分别使切出的方块的上面/前面/右面是正方形的面。考虑其中的一种姿势，我们可以O(n^2)枚举正方形的面在原先的大立方体中的右下角坐标(i,j),那么大正方体的每一层中以(i,j)为右下角的完好正方形都有一个最大边长,我们把这些最大边长拿出来形成一个序列。因为最优方案中一定有一个位置的正方形达到了最大边长(否则一定可以得到边长更大的解),所以我们枚举达到最大边长的正方形在哪个位置,找出它最多向两边延伸到哪里,也就是找到两边第一个比它小的最大边长的位置,这一步可以单调栈O(n)枚举所有位置.加起来是O(n^3)
中间还有一步,求以每个位置为右下角的完好正方形最大边长。记某一层以(i,j)为右下角的完好正方形最大边长为f[i][j]，那么f[i][j]<=f[i-1][j-1]+1因此我们从f[i-1][j-1]+1开始从大到小枚举f[i][j]的可能取值，只需判断比f[i-1][j-1]多出来的那一部分(第i行和第j列的对应位置)是否全部完好无损即可,找到第一个合法的结果时就跳出循环.每一层的DP看起来都是O(n^3)的，但其实是O(n^2)的。考虑f[1][2],f[2][3],f[3][4],f[4][5]…..,它们所对应的最大完好正方形的上边界是单调下降的,因此对于这一条斜线上的所有状态总的枚举量为O(n).斜线的数目也是O(n)的，因此一层的复杂度是O(n^2),一共n层, DP的总复杂度为O(n^3)
枚举挖方块的姿势的时候,我的写法比较丑,认为是把输入的大立方体旋转到三种不同的姿势,每次都让削出的正方形的面在y轴和z轴确定的平面内(也就是说，分别让大立方体的上面/前面/右面位于yOz平面内)。实现的时候写了三个在不同坐标系下找到对应位置的函数,计算的时候把函数指针传进去,高维数组寻址常数炸天…
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
char str[maxn][maxn][maxn];
//三种切木块的姿势
char get1(int x,int y,int z){
return str[x][y][z];
}
char get2(int x,int y,int z){
return str[y][x][z];
}
char get3(int x,int y,int z){
return str[y][z][x];
}
int f[maxn][maxn][maxn];//f[i][j][k]:第i层的(j,k)为右下角的最大完好正方形
int sum[maxn][maxn];
void dp(int f[maxn][maxn],int x,int n,int m,char getc(int,int,int)){
for(int i=;i<=n;++i){
for(int j=;j<=m;++j){
// if(getc(x,i,j)=='P')printf("%d %d %d\n",x,i,j);
sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+(getc(x,i,j)=='P');
}//sum[i][j]:在(i,j)左上方有多少坏格子
}//printf("%d\n",sum[n][m]);
for(int i=;i<=n;++i){
for(int j=;j<=m;++j){
for(int k=f[i-][j-]+;k>=;--k){
if(sum[i][j]-sum[i-][j]-sum[i][j-k]+sum[i-][j-k]==&&sum[i][j]-sum[i][j-]-sum[i-k][j]+sum[i-k][j-]==){
f[i][j]=k;
break;
}
}
}
}
}
int s[maxn],top=;
int rbound[maxn],lbound[maxn];//lbound:某个位置向左数第一个比它小的位置 rbound:某个位置向右数第一个比它小的位置
int work(int maxx,int maxy,int maxz,char getc(int,int,int)){
for(int i=;i<=maxx;++i){
dp(f[i],i,maxy,maxz,getc);//把第i层搞出来
}
int ans=;
for(int i=;i<=maxy;++i){
for(int j=;j<=maxz;++j){
top=;
s[]=;
for(int k=;k<=maxx;++k){
while(top!=&&f[k][i][j]<=f[s[top]][i][j])--top;
lbound[k]=s[top];
s[++top]=k;
}
s[]=maxx+;
top=;
for(int k=maxx;k>=;--k){
while(top!=&&f[k][i][j]<=f[s[top]][i][j])--top;
rbound[k]=s[top];
s[++top]=k;
}
for(int k=;k<=maxx;++k){
ans=max(ans,*(rbound[k]-lbound[k]-)*f[k][i][j]);
// if(4*(rbound[k]-lbound[k]-1)*f[k][i][j]==40)printf("%d %d %d %d %d\n",rbound[k]-lbound[k]-1,f[k][i][j],k,i,j);
}
}
}//printf("%d\n",ans);
return ans;
}
int main(){
int p,q,r;scanf("%d%d%d",&q,&p,&r);
for(int i=;i<=p;++i){//没有读懂题目的坐标描述...瞎读呗,读错了也就相当于把坐标系换了一下
for(int j=;j<=q;++j){
scanf("%s",str[i][j]+);
}//printf("\n");
}
int ans=;
ans=max(ans,work(p,q,r,get1));
ans=max(ans,work(q,p,r,get2));
ans=max(ans,work(r,p,q,get3));
printf("%d\n",ans);
return ;
}