bzoj1057: [ZJOI2007]棋盘制作（悬线法）

时间：2023-03-09 05:52:15
bzoj1057: [ZJOI2007]棋盘制作（悬线法）

　　题目要求纵横坐标和奇偶性不同的点取值不同，于是我们把纵横坐标和奇偶性为1的点和0的点分别取反，就变成经典的最大全1子矩阵问题了，用悬线法解决。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int maxn=,inf=1e9;

int n,m,ans1,ans2;

int h[maxn],mp[maxn][maxn],l[maxn],r[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int sqr(int x){return x*x;}

void dp()

{

    memset(h,,(m+)<<);

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

    {

        for(int j=;j<=m;j++)

        if(mp[i][j])h[j]++;else h[j]=;

        for(int j=;j<=m;j++)

        if(mp[i][j])

        for(l[j]=j;h[j]<=h[l[j]-]&&mp[i][l[j]-];l[j]=l[l[j]-]);

        for(int j=m;j;j--)

        if(mp[i][j])

        for(r[j]=j;h[j]<=h[r[j]+]&&mp[i][r[j]+];r[j]=r[r[j]+]);

        for(int j=;j<=m;j++)

        ans1=max(ans1,(r[j]-l[j]+)*h[j]);

        for(int j=;j<=m;j++)

        ans2=max(ans2,min(sqr(r[j]-l[j]+),sqr(h[j])));

    }

}

int main()

{

    read(n);read(m);

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

    for(int j=;j<=m;j++)

    read(mp[i][j]),mp[i][j]=((i+j)&?mp[i][j]:!mp[i][j]);

    dp();

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

    for(int j=;j<=m;j++)mp[i][j]=!mp[i][j];

    dp();

    printf("%d\n%d",ans2,ans1);

}

相关文章