Đề 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):
Để 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:
- Pascal : https://ideone.com/qWOX4q
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. |
Speak Your Mind