蒟蒻求助,关于这题的做法
查看原帖
蒟蒻求助,关于这题的做法
196899
lndjy楼主2020/6/12 20:20

蒟蒻写了一个和题解不一样的做法,就是先对每层跑一遍最大子矩形,然后再用向上更新的方法去更新第三维。

但是样例都没过,比答案小。

所以是我思路根本就不行,还是可以改,如果是前者,蒟蒻想知道为什么,如果是后者,蒟蒻想知道怎么改。

不排除我是sb的可能性

代码:

#include<iostream>
using namespace std;
int a[155][155][155],l[155][155][155],r[155][155][155],up[155][155][155],upp[155][155][155];
int n,m,o;
int getans(int x,int y,int z)
{
	int f=0,s=0,t=0;
	if(x>=f) t=s,s=f,f=x;else if(x>=s) t=s,s=x;else t=x;
	if(y>=f) t=s,s=f,f=y;else if(y>=s) t=s,s=y;else t=y;
	if(z>=f) t=s,s=f,f=z;else if(z>=s) t=s,s=z;else t=z;
	return f*t; 
}
int main()
{
	cin>>n>>m>>o;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	for(int k=1;k<=o;k++)
	{
		char c;
		cin>>c;
		a[i][j][k]=(c=='N');
		if(a[i][j][k])
		{
			l[i][j][k]=r[i][j][k]=k;
			up[i][j][k]=1;
			upp[i][j][k]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		for(int k=2;k<=o;k++)
		if(a[i][j][k]&&a[i][j][k-1])
		l[i][j][k]=l[i][j][k-1];
		for(int j=1;j<=m;j++)
		for(int k=o-1;k>=1;k--)
		if(a[i][j][k]&&a[i][j][k+1])
		r[i][j][k]=r[i][j][k+1];
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		for(int k=1;k<=m;k++)
		{
			if(j>1&&a[i][j][k]&&a[i][j-1][k])
			{
				l[i][j][k]=max(l[i][j][k],l[i][j-1][k]);
				r[i][j][k]=min(r[i][j][k],r[i][j-1][k]);
				up[i][j][k]=up[i][j-1][k]+1;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		for(int k=1;k<=m;k++)
		{
			if(i>1&&a[i][j][k]&&a[i-1][j][k])
			{
				l[i][j][k]=max(l[i][j][k],l[i-1][j][k]);
				r[i][j][k]=min(r[i][j][k],r[i-1][j][k]);
				up[i][j][k]=min(up[i][j][k],up[i-1][j][k]);
				upp[i][j][k]=upp[i-1][j][k]+1;
			}
			x=r[i][j][k]-l[i][j][k]+1,y=up[i][j][k],z=upp[i][j][k];
			ans=max(ans,getans(x,y,z));
		}
	}
	cout<<ans*4;
	return 0;
}
2020/6/12 20:20
加载中...