bzoj 3039 悬线法求最大01子矩阵

时间:2021-10-10 03:26:46

首先预处理每个F点左右,下一共有多少个F点,然后

对于每个为0的点(R),从这个点开始,一直到这个点

下面第一个R点,这一区间中的min(左),min(右)更新答案。

ps:我估计这道题数据有的格式不对,开始过不去,后来改了读入

就能过了

/**************************************************************
    Problem:
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time: ms
    Memory: kb
****************************************************************/
 
//By BLADEVIL
var
    n, m                        :longint;
    map                         :array[..,..] of longint;
    ans, len1, len, len2        :longint;
    left, right, down           :array[..,..] of longint;
     
function max(a,b:longint):longint;
begin
    if a>b then max:=a else max:=b;
end;
 
function min(a,b:longint):longint;
begin
    if a>b then min:=b else min:=a;
end;
     
procedure init;
var
    i, j, k                     :longint;
    ss                          :ansistring;
begin
    readln(n,m);
    for i:= to n do
    begin
        readln(ss);
        k:=;
        for j:= to length(ss) do
            if ss[j]<>' ' then
            begin
                inc(k);
                if ss[j]='F' then map[i,k]:= else map[i,k]:=;
            end;
    end;
     
    for i:= to n do
        for j:= to m do
            if map[i,j]= then left[i,j]:= else left[i,j]:=left[i,j-]+;
             
    for i:=n downto do
        for j:=m downto do
        begin
            if map[i,j]= then down[i,j]:= else down[i,j]:=down[i+,j]+;
            if map[i,j]= then right[i,j]:= else right[i,j]:=right[i,j+]+;
        end;
     
end;
 
procedure main;
var
    i, j, k                     :longint;
begin
    for i:= to n do
        for j:= to m do
            if map[i,j]= then
            begin
                len:=;
                len1:=maxlongint div ;
                len2:=maxlongint div ;
                for k:= to down[i+,j] do
                begin
                    len1:=min(len1,left[i+k,j]);
                    len2:=min(len2,right[i+k,j]);
                    ans:=max(ans,(len1+len2-)*k);
                end;
                if len1>=maxlongint div then continue;
                inc(len,len1);
                ans:=max(ans,(len-)*down[i+,j]);
            end;
    writeln(ans*);
end;
 
begin
    init;
    main;
end.