1 条题解

  • 1
    @ 2022-7-16 21:45:03
    #include<bits/stdc++.h>
    #define IL inline
    #define RI register int
    #define maxn 2001
    using namespace std;
    IL void read(int &x){
    	int f=1;x=0;char s=getchar();
    	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    	while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
    	x*=f;
    }
    int res[maxn][maxn],left[maxn][maxn],right[maxn][maxn],up[maxn][maxn];
    int n,m,ans1,ans2;
    int main()
    {
    	read(n),read(m);
    	for(RI i=1;i<=n;i++)
    		for(RI j=1;j<=m;j++)
    			{
    				read(res[i][j]);
    				left[i][j]=right[i][j]=j;
    				up[i][j]=1;
    			}
    	for(RI i=1;i<=n;i++)
    		for(RI j=2;j<=m;j++)
    			if(res[i][j]!=res[i][j-1])
    				left[i][j]=left[i][j-1];//预处理左边界
    	for(RI i=1;i<=n;i++)
    		for(RI j=m-1;j>0;j--)
    			if(res[i][j]!=res[i][j+1])
    				right[i][j]=right[i][j+1];//预处理右边界
    	for(RI i=1;i<=n;i++)
    		for(RI j=1;j<=m;j++)
    			{
    				if(i>1&&res[i][j]!=res[i-1][j])
    				{
    					left[i][j]=max(left[i][j],left[i-1][j]);
    					right[i][j]=min(right[i][j],right[i-1][j]);
    					up[i][j]=up[i-1][j]+1;
    				}
    				int a=right[i][j]-left[i][j]+1;	//横向长度
    				int b=min(a,up[i][j]);//竖向长度
    				//printf("a:%d b:%d\n",a,b);
    				ans1=max(ans1,b*b);//正方形
    				ans2=max(ans2,a*up[i][j]);//长方形
    			}
    	printf("%d\n%d",ans1,ans2);
    }
    
    • 1

    信息

    ID
    170
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    7
    已通过
    3
    上传者