题解 P1169 【[ZJOI2007]棋盘制作】

· · 题解

首先把矩阵转化一下，把横纵坐标和为偶数点的值取反，这样就转化成求最大的'0'或'1'矩阵。

我们只讨论对于0的求法，对1类似。

首先是最大正方形问题，这是一个经典的DP问题，f[i,j]表示以i,j为右下角的最大正方形的边长，那么a[i,j]=0时，f[i,j]=min(f[i-1,j-1],f[i-1,j],f[i,j-1])+1，a[i,j]=1时，f[i,j]=0，f数组中的最大值即为第一问的答案。

对于第二问，我们用一个单调栈来解决。

首先枚举最大矩形的下边界，对于每一个下边界维护两个（也可以说是两次）单调栈，一次正向，一次反向，用s[i,j]表示从a[i,j]开始向上最多能扩展出几个0，如果a[i,j]=1，那么s[i,j]=0，这样维护栈中元素的s值递增，每次元素出栈时就可以确定这个元素可以向左或向右扩展多少长度了，即找到了第一个s值小于该元素的位置，然后用每个元素的s值乘以向左向右扩展的长度和去更新第二问的答案就可以了。

由于每个元素最多进栈或出栈一次，每次的复杂度为O(n)，这样总的时间复杂度就是O(n^2);

参考代码


var s,f:array[0..2001,0..2001]of longint;
    a:array[0..2001,0..2001]of 0..1;
    z,l,r,p:array[0..2001]of longint;
    ans1,ans2,i,j,m,n,k,t:longint;
function max(a,b:longint):longint;
begin if a>b then exit(a) else exit(b); end;
function min(a,b:longint):longint;
begin if a<b then exit(a) else exit(b); end;
procedure dp(o:longint);
var i,j:longint;
begin
  for i:=1 to n do if a[1,i]=o then s[1,i]:=1;
  for i:=2 to m do
    for j:=1 to n do
      if a[i,j]=o
      then s[i,j]:=s[i-1,j]+1 else s[i,j]:=0;
  for i:=1 to m do
    for j:=1 to n do
      begin
        if a[i,j]=o
        then f[i,j]:=min(f[i-1,j-1],min(f[i-1,j],f[i,j-1]))+1
        else f[i,j]:=0;
        ans1:=max(ans1,f[i,j]);
      end;
  for i:=1 to m do
    begin
      fillchar(l,sizeof(l),0);
      fillchar(r,sizeof(r),0);
      t:=0;
      for j:=1 to n do
        begin
          while (t>0)and(s[i,j]<s[i,z[t]]) do
            begin
              r[z[t]]:=j-z[t];
              dec(t);
            end;
          if a[i,j]=o
          then
            begin
              inc(t);
              z[t]:=j;
            end;
        end;
      for j:=t downto 1 do r[z[j]]:=n-z[j]+1;
      t:=0;
      for j:=n downto 1 do
        begin
          while (t>0)and(s[i,j]<s[i,z[t]]) do
            begin
              l[z[t]]:=z[t]-j;
              dec(t);
            end;
          if a[i,j]=o
          then
            begin
              inc(t);
              z[t]:=j;
            end;
        end;
      for j:=t downto 1 do l[z[j]]:=z[j];
      for j:=1 to n do
        if a[i,j]=o
        then
          begin
            p[j]:=l[j]+r[j]-1;
            ans2:=max(ans2,p[j]*s[i,j]);
          end;
    end;
end;
begin
  readln(m,n);
  for i:=1 to m do
    for j:=1 to n do
      begin
        read(a[i,j]); if (i+j) mod 2=0 then a[i,j]:=1-a[i,j];
      end;
  dp(0); dp(1);
  writeln(ans1*ans1); writeln(ans2);
end.