NC20497. [ZJOI2011]礼物(GIFT)
描述
输入描述
每个输入文件中仅包含一个测试数据。
第一行包含三个由空格隔开的正整数，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的值。
示例1
输入:
3 2 5 PNNNN PNNNN NPPNP PNNNP NNNNP PPNNP
输出:
24
C++11(clang++ 3.9) 解法, 执行用时: 389ms, 内存消耗: 42176K, 提交时间: 2020-09-24 19:18:49
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=155;
int a[N][N][N],b[N][N][N],s[N][N],len[N][N][N],st[N],L[N],R[N],ans;char str[N];
bool check(int x,int y,int x2,int y2){return s[x2][y2]-s[x-1][y2]-s[x2][y-1]+s[x-1][y-1]==(x2-x+1)*(x2-x+1);}
void solve(int p,int q,int r){
for(int k=1,now;k<=r;k++){
for(int i=1;i<=p;i++)for(int j=1;j<=q;j++)
s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j][k]-s[i-1][j-1];
now=0;
for(int i=1;i<=p;i++)for(int j=1;j<=q;j++){
while(i+now<=p&&j+now<=q&&check(i,j,i+now,j+now))now++;
len[i][j][k]=now;if(now>0)now--;
}
}
for(int i=1;i<=p;i++)for(int j=1,tp;j<=q;j++){
tp=0;
for(int k=1;k<=r;k++){
while(tp&&len[i][j][st[tp]]>=len[i][j][k])tp--;
if(tp)L[k]=st[tp]+1;else L[k]=1;
st[++tp]=k;
}
tp=0;
for(int k=r;k;k--){
while(tp&&len[i][j][st[tp]]>=len[i][j][k])tp--;
if(tp)R[k]=st[tp]-1;else R[k]=r;
st[++tp]=k;
}
for(int k=1;k<=r;k++)ans=max(ans,len[i][j][k]*(R[k]-L[k]+1));
}
}
int main(){
int p,q,r;scanf("%d%d%d",&q,&p,&r);
for(int i=1;i<=p;i++)for(int j=1;j<=q;j++){
scanf("%s",str+1);
for(int k=1;k<=r;k++)b[i][j][k]=str[k]=='N';
}
memcpy(a,b,sizeof(a));
solve(p,q,r);
for(int i=1;i<=p;i++)for(int j=1;j<=r;j++)for(int k=1;k<=q;k++)a[i][j][k]=b[i][k][j];
solve(p,r,q);
for(int i=1;i<=q;i++)for(int j=1;j<=r;j++)for(int k=1;k<=p;k++)a[i][j][k]=b[k][i][j];
solve(q,r,p);
printf("%d\n",ans<<2);
return 0;
}