洛谷 P1169 [ZJOI2007]棋盘制作

时间:2022-02-11 09:24:28

2016-05-31 14:56:17

题目链接: 洛谷 P1169 [ZJOI2007]棋盘制作

题目大意:

  给定一块矩形,求出满足棋盘式黑白间隔的最大矩形大小和最大正方形大小

解法:

  神犇王知昆的悬线法

  论文:浅谈用极大化思想解决最大子矩形问题

  H[i][j]表示(i,j)向上最长连续多少距离不出现障碍点(悬线)

  L[i][j]表示H[i][j]这根悬线最多可以向左移到什么位置

  R[i][j]表示H[i][j]这根悬线最多可以向右移到什么位置

  递推方式看代码吧,很好理解的

 //棋盘制作 (ZJOI2007)
//悬线法 矩形DP
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=;
int H[maxn][maxn];
int L[maxn][maxn];
int R[maxn][maxn];
bool map[maxn][maxn];
int N,M;
int ans1;
int ans2;
int main()
{
scanf("%d %d",&N,&M);
for(int i=;i<=N;i++)
{
for(int j=;j<=M;j++)
{
int x;
scanf("%d",&x);
map[i][j]=x;
if(i==)H[i][j]=;
else if(map[i][j]!=map[i-][j])H[i][j]=H[i-][j]+;
else H[i][j]=;
}
}
for(int i=;i<=N;i++)
{
for(int j=;j<=M;j++)
{
L[i][j]=j;
while(L[i][j]>&&map[i][L[i][j]-]!=map[i][L[i][j]]&&H[i][L[i][j]-]>=H[i][j])
{
L[i][j]=L[i][L[i][j]-];
}
}
for(int j=M;j>=;j--)
{
R[i][j]=j;
while(R[i][j]<M&&map[i][R[i][j]+]!=map[i][R[i][j]]&&H[i][R[i][j]+]>=H[i][j])
{
R[i][j]=R[i][R[i][j]+];
}
}
for(int j=;j<=M;j++)
{
int dx=R[i][j]-L[i][j]+;
int dy=H[i][j];
ans1=max(ans1,dx*dy);
ans2=max(ans2,min(dx,dy)*min(dx,dy));
}
}
printf("%d\n%d",ans2,ans1);
}