【BZOJ2228】[ZJOI2011]礼物（单调栈）

题面

题解

如果这个玩意不是一个三维立方体，而是一个二维的矩形，让你在里面找一个最大正方形，那么全世界都会做。

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

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

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

然而我想了半天怎么求以某个点为左上角的最大正方形，就像萝卜求助，然后被萝卜狠狠狠狠狠的批判了一番：“不就搞个变量扫一遍就好了吗？”，我“？？？”（智商掉线.jpg，最近智商已经没了，要找点智商了。）

大概是这样的：按照某一行来做，从左往右确定每一列的答案，暴力拓展最大的合法正方形，假设边长为\(N\)，那么往右移一个位置的时候直接从\(N-1\)还是枚举就好了。我实在是太菜了，这都不会。

注意一下他这个字符串的读入顺序并不是\(pqr\)，而是\(qpr\)。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 155

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

char g[MAX][MAX][MAX];

int s[MAX][MAX][MAX];

int n[MAX][MAX][MAX];

int p[MAX][MAX];

int L[MAX],R[MAX],Q[MAX],H,T;

int a,b,c,ans;

bool check(int b,int c,int x,int y,int N)

{

	if(x+N-1>b||y+N-1>c)return false;

	int xx=x+N-1,yy=y+N-1;

	return p[xx][yy]-p[xx][y-1]-p[x-1][yy]+p[x-1][y-1]==N*N;

}

void Calc(int a,int b,int c)

{

	for(int i=1;i<=a;++i)

	{

		for(int j=1;j<=b;++j)

			for(int k=1;k<=c;++k)

				p[j][k]=s[i][j][k]+p[j-1][k]+p[j][k-1]-p[j-1][k-1];

		for(int j=1;j<=b;++j)

		{

			int N=0;

			for(int k=1;k<=c;++k)

			{

				while(check(b,c,j,k,N+1))++N;

				n[i][j][k]=N;N-=1;

			}

		}

	}

	for(int j=1;j<=b;++j)

		for(int k=1;k<=c;++k)

		{

			T=0;

			for(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(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(int i=1;i<=a;++i)

				ans=max(ans,n[i][j][k]*(R[i]-L[i]+1));

		}

}

int main()

{

	b=read();a=read();c=read();

	for(int i=1;i<=a;++i)

		for(int j=1;j<=b;++j)

			scanf("%s",g[i][j]+1);

	for(int i=1;i<=a;++i)

		for(int j=1;j<=b;++j)

			for(int k=1;k<=c;++k)

				s[i][j][k]=(g[i][j][k]=='N');

	Calc(a,b,c);

	for(int i=1;i<=b;++i)

		for(int j=1;j<=a;++j)

			for(int k=1;k<=c;++k)

				s[i][j][k]=(g[j][i][k]=='N');

	Calc(b,a,c);

	for(int i=1;i<=c;++i)

		for(int j=1;j<=b;++j)

			for(int k=1;k<=a;++k)

				s[i][j][k]=(g[k][j][i]=='N');

	Calc(c,b,a);

	printf("%d\n",4*ans);

	return 0;

}

巴特西

【BZOJ2228】[ZJOI2011]礼物（单调栈）

【BZOJ2228】[ZJOI2011]礼物（单调栈）

题面

题解

最新文章

热门文章