QBRECT spoj – Hình chữ nhật 0 1
Nguồn đề bài: http://vn.spoj.com/problems/QBRECT/ Đề bài QBRECT spoj Cho một bảng kích thước MxN, được chia thành lưới ô vuông đơn vị M dòng N cột ( 1 <= M, N <= 1000 ) Trên các ô của bảng ghi số 0 hoặc 1. Các dòng của bảng được đánh số 1, 2… M theo thứ tự từ trên ...
Nguồn đề bài: http://vn.spoj.com/problems/QBRECT/
Đề bài QBRECT spoj
Cho một bảng kích thước MxN, được chia thành lưới ô vuông đơn vị M dòng N cột ( 1 <= M, N <= 1000 )
Trên các ô của bảng ghi số 0 hoặc 1. Các dòng của bảng được đánh số 1, 2… M theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số 1, 2…, N theo thứ tự từ trái qua phải
Yêu cầu:
Hãy tìm một hình chữ nhật gồm các ô của bảng thoả mãn các điều kiện sau:
1 – Hình chữ nhật đó chỉ gồm các số 1
2 – Cạnh hình chữ nhật song song với cạnh bảng
3 – Diện tích hình chữ nhật là lớn nhất có thể
Input
Dòng 1: Ghi hai số M, N
M dòng tiếp theo, dòng thứ i ghi N số mà số thứ j là số ghi trên ô (i, j) của bảng
Output
Gồm 1 dòng duy nhất ghi diện tích của hình chữ nhật tìm được
Example
Input:
11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1
Output:
49
THUẬT TOÁN
code pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | const fi='; nmax=1000; type data=longint; var f:text; A:array[0..nmax+1,0..nmax+1] of byte; n,test,m:data; sta:data; H:array[0..nmax*nmax+1] of data; D,L,R:array[0..nmax+1] of data; procedure docfile; var i,j:data; begin assign(f,fi);reset(f); readln(f,m,n); for i:=1 to m do for j:=1 to n do read(f,a[i,j]); close(f); end; function xem:data; begin exit(h[sta]); end; procedure them(x:data); begin inc(sta); h[sta]:=x; end; function lay:data; begin lay:=h[sta]; dec(sta); end; procedure xuli; var i,j,res,dt:data; begin fillchar(d,sizeof(d),0); res:=0; sta:=0; for i:=1 to m do begin for j:=1 to n do if a[i,j]<>1 then d[j]:=i; sta:=0; for j:=1 to n do begin while (sta>0) and (D[xem]<=D[j]) do lay; if sta=0 then L[j]:=0 else L[j]:=xem; them(j); end; sta:=0; for j:=n downto 1 do begin while (sta>0) and (d[xem]<=d[j]) do lay; if sta=0 then R[j]:=n+1 else R[j]:=xem; them(j); end; for j:=1 to n do begin dt:=(i-d[j])*(R[j]-L[j]-1); if dt>res then res:=dt; end; end; writeln(res); end; begin docfile; xuli; readln; end. |
code c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <iostream> #include <fstream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> using namespace std; #define maxn 1010 int n , m , a[maxn][maxn]; int h[maxn] , l[maxn] , r[maxn] , res; int main() { scanf("%d%d",&m,&n); for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]); h[0] = -1; h[n+1] = -1; for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) h[j] = a[i][j] * (h[j] + 1); for (int j=1;j<=n;j++) { l[j] = j; while (h[l[j]-1] >= h[j]) l[j] = l[l[j]-1]; } for (int j=n;j>0;j--) { r[j] = j; while (h[r[j]+1] >= h[j]) r[j] = r[r[j]+1]; } for (int j=1;j<=n;j++) res = max(res,h[j]*(r[j]-l[j]+1)); } printf("%d",res); } |
