fengyunfly吧 关注:9贴子:102
  • 0回复贴,共1

Award

收藏回复

  • 218.5.1.*
program award;
var hmax,c,d,e,i,j,k,m,n,x,y:longint;
    a:array[1.. 200,1.. 200] of boolean;
    f,h:array[1.. 200,1.. 200] of longint;
    g2:array[1.. 200,1.. 200,1.. 200] of longint;
    fan,dp:array[0.. 200,0.. 200,1.. 201] of longint;
function max(p,q:longint):longint;
begin
  max:=p;
  if q>max then max:=q;
end;

function maxt(p,q,r:longint):longint;
begin
  maxt:=p;
  if q>maxt then maxt:=q;
  if r>maxt then maxt:=r;
end;

begin
  assign(input,'award.in');
  assign(output,'award.out');
  reset(input);
  rewrite(output);
  read(n,m);
  fillchar(a,sizeof(a),false);
  fillchar(f,sizeof(f),0);
  fillchar(g2,sizeof(g2),0);
  fillchar(fan,sizeof(fan),0);
  fillchar(dp,sizeof(dp),0);
  y:=0;
  for i:=1 to n do begin
    for j:=1 to m do begin
      read©;
      if c=0 then begin
        a[i,j]:=true;
      end
      else
        y:=1;
    end;
  end;
  if y=0 then begin
    writeln('39998');
    close(input);
    close(output);
    halt;
  end;
  for i:=1 to n do begin
    hmax:=0;
    for j:=1 to m do begin
      if a[i,j] then begin
        inc(hmax);
        h[i,j]:=hmax;
        for k:=hmax downto 1 do begin
          fan[i,j-k+1,j]:=k+fan[i-1,j-k+1,j];
        end;
      end
      else begin
        hmax:=0;
      end;
    end;
  end;
  for i:=1 to n do begin
    for k:=m-2 downto 1 do begin
      for j:=2 to m-k do begin
        dp[i,j,j+k-1]:=maxt(dp[i,j-1,j+k-1],dp[i,j,j+k],fan[i,j-1,j+k]);
      end;
    end;
  end;
  for i:=2 to n do begin
    for j:=2 to m-1 do begin
      if a[i,j] then begin
        for k:=h[i,j] downto 1 do begin
          g2[i,j-k+1,j]:=max(g2[i-1,j-k+1,j],dp[i-1,j-k+1,j]);
          if g2[i,j-k+1,j]>0 then begin
            inc(g2[i,j-k+1,j],k);
          end;
        end;
      end;
    end;
  end;
  fillchar(fan,sizeof(fan),0);
  for i:=n downto 1 do begin
    hmax:=0;
    for j:=1 to m do begin
      if a[i,j] then begin
        inc(hmax);
        h[i,j]:=hmax;
        for k:=hmax downto 1 do begin
          fan[i,j-k+1,j]:=k+fan[i+1,j-k+1,j];
        end;
      end
      else begin
        hmax:=0;
      end;
    end;
  end;
  fillchar(dp,sizeof(dp),0);
  for i:=n downto 1 do begin
    for k:=m-2 downto 1 do begin
      for j:=2 to m-k do begin
        dp[i,j,j+k-1]:=maxt(dp[i,j-1,j+k-1],dp[i,j,j+k],fan[i,j-1,j+k]);
      end;
    end;
  end;
  c:=0;
  for i:=2 to n-1 do begin
    for j:=2 to m-1 do begin
      if a[i,j] then begin
        for k:=h[i,j] downto 1 do begin
          if c<(g2[i,j-k+1,j]+dp[i+1,j-k+1,j]) then begin
            c:=g2[i,j-k+1,j]+dp[i+1,j-k+1,j];
          end;
        end;
      end;
    end;
  end;
  writeln©;
  close(input);
  close(output);
end.



1楼2008-05-24 13:53回复