[BZOJ1057][ZJOI2007]棋盘制作

LG题目链接

BZOJ题目链接

题目大意

给定一个n*m的矩阵，求最大符合条件的矩阵和长方形。符合条件的矩阵为相邻两个元素不相同且矩阵内元素只为1或0。

solution

由于是求最大子矩阵 所以可以用到悬线法。

所谓悬线法，就是对于矩阵内每个点（i，j），求出向左（右）所能符合条件扩展的最左（右）位置。也可以求最上的位置。

我们可以假设Lij，R_ij，UP_ij 为点（i，j）所能扩展到的最左，最右，最上的位置。那么对于L_ij，R_ij 有

L_{i,j}=L_{i,j-1}[m_{i,j}!=m_{i,j-1}](1<j<=m)

R_{i,j}=R_{i,j+1}[m_{i,j}!=m_{i,j+1}](m>j>=1)

然后我们考虑上下的情况，有

L_{i,j}=max(L_{i,j},L_{i-1,j})

R_{i,j}=min(R_{i,j},R_{i-1,j})

UP_{i,j}=UP_{i-1,j}+1;

满足条件

[m_{i,j}!=m_{i-1,j}](1<i<=n)

因为当L取max R取min时，能接上的为极大子矩阵,也就是无法再扩展了。要是上一行合法，显然可以进行转移。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2010;
int mp[maxn][maxn],l[maxn][maxn],r[maxn][maxn],up[maxn][maxn],ans1,ans2;
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&mp[i][j]);
l[i][j]=r[i][j]=j;
up[i][j]=1;
}
}
for(int i=1;i<=n;i++)
for(int j=2;j<=m;j++)
if(mp[i][j]!=mp[i][j-1])l[i][j]=l[i][j-1];
for(int i=1;i<=n;i++)
for(int j=m-1;j>=1;j--)
if(mp[i][j]!=mp[i][j+1])r[i][j]=r[i][j+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(i!=1&&mp[i][j]!=mp[i-1][j])
{
up[i][j]=up[i-1][j]+1;
l[i][j]=max(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
}
ans1=max(ans1,min(r[i][j]-l[i][j]+1,up[i][j])*min(r[i][j]-l[i][j]+1,up[i][j]));
ans2=max(ans2,(r[i][j]-l[i][j]+1)*up[i][j]);
}
cout<<ans1<<endl<<ans2<<endl;
return 0;
}

[BZOJ1057][ZJOI2007]棋盘制作

原文：https://www.cnblogs.com/-DDF-/p/11988557.html