QBRECT – spoj

21/09/2017 by Leave a Comment

Đề bài:

Thuật toán:

Sau đây là cách tìm hình chữ nhật lớn nhất trong thời gian O(n^2):

Với mỗi ô j trên hàng i, ta tìm f(j) là số ô 1 liên tiếp trên cột j, tính từ hàng i trở lên. Sau đó, với mỗi cột j, ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có f nhỏ hơn f(j), sau đó tính diện tích hình chữ nhật ở cột j là S=f(j)×(r−l−1) với l,r là chỉ số 2 ô bên trái và bên phải nói trên.
Hình minh hoạ khi tính f(4):
deque-yeulaptrinh.pw
Để tìm l,r nhanh, ta dùng kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

Code:

uses    math;
const   fi='';
        fo='';
        maxn=1000;
var     a:array[1..maxn,1..maxn] of byte;
        i,j,m,n,res,top:longint;
        h,s,left,right:array[1..maxn] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    close(input);
end;
procedure push(x:integer);
begin
    inc(top);
    s[top]:=x;
end;
function get:integer;
begin
    exit(s[top]);
end;
procedure pop;
begin
    dec(top);
end;
procedure xuly;
begin
    for i:=1 to m do
     begin
        for j:=1 to n do
           if a[i,j]=1 then
                begin
                    h[j]:=h[j]+1;
                end else h[j]:=0;
        top:=0;
        for j:=1 to n do
            begin
                while (top<>0) and (h[j]<=h[get]) do pop;
                if top=0 then left[j]:=0 else left[j]:=get;
                push(j);
            end;
        top:=0;
        for j:=n downto 1 do
                begin
                    while (top<>0) and (h[j]<=h[get]) do pop;
                    if top=0 then right[j]:=n+1 else right[j]:=get;
                    push(j);
                end;
        for j:=1 to n do
                begin
                    res:=max(res,h[j]*(right[j]-left[j]-1));
                end;
     end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
end.
Chủ đề: Deque Mức độ:
Khuyên dùng

 

Speak Your Mind

*