CodeDevil

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1057

【题意】

给定一个n*m的棋盘，求最大的01相间的矩形和正方形面积。

【题解】

在一个01相间的棋盘里，黑色格点的行列坐标奇偶性相同。

我们把行列坐标奇偶性相同的点颜色取反，然后计算新的棋盘上面积最大的相同颜色的矩形和正方形。

因为我写的是计算给定棋盘上面积最大的颜色为1的矩形和正方形，所以计算一次后还要把整个棋盘颜色反转再计算一遍。

计算最大面积，可以用dp和单调队列搞一搞。

【代码】

#include <iostream>

#include <cstdio>

#include <string>

using namespace std;

 

int m,n,top,i,j,ans1,ans2,H[2010][2010],q[2010],L[2010],R[2010];

bool a[2010][2010];

 

void Max_area()

{

    ans1=0,ans2=0;

    for (i=1;i<=n;i++)

        H[0][i]=0;

    for (i=1;i<=m;i++)

        for (j=1;j<=n;j++)

            if (!a[i][j])

                H[i][j]=0;

            else

                H[i][j]=H[i-1][j]+1;

    for (i=1;i<=m;i++)

    {

        top=0;q[top]=0;

        for (j=1;j<=n;j++)

        {

            if (!a[i][j])

            {

                top=1;q[top]=j;L[j]=0;

                continue;

            }

            while (top>0 && H[i][j]<=H[i][q[top]])

                top--;

            L[j]=j-q[top];top++;q[top]=j;

        }

        top=0;q[top]=n+1;

        for (j=n;j>0;j--)

        {

            if (!a[i][j])

            {

                top=1;q[top]=j;R[j]=0;

                continue;

            }

            while (top>0 && H[i][j]<=H[i][q[top]])

                top--;

            R[j]=q[top]-j-1;top++;q[top]=j;

        }

         

        for (j=1;j<=n;j++)

        {

            ans1=max(ans1,H[i][j]*(L[j]+R[j]));

            ans2=max(ans2,min(H[i][j],(L[j]+R[j]))*min(H[i][j],(L[j]+R[j])));

        }

    }

}

 

int main()

{

    int ans3,ans4,ans5,ans6;

    scanf("%d%d",&m,&n);

    for (i=1;i<=m;i++)

        for (j=1;j<=n;j++)

        {

            scanf("%d",&a[i][j]);

            if (i%2==j%2) a[i][j]=1-a[i][j];

        }

    Max_area();

    ans3=ans1,ans4=ans2;

    for (i=1;i<=m;i++)

        for (j=1;j<=n;j++)

            a[i][j]=1-a[i][j];

    Max_area();

    ans5=ans1,ans6=ans2;

    printf("%d\n%d\n",max(ans4,ans6),max(ans3,ans5));

    return 0;

}