Hướng dẫn giải của Hình chữ nhật 0 1
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; maxn=1010; var m,n,re:longint; a:array[0..maxn,0..maxn] of longint; st,pos:array[0..2*maxn] of longint; procedure rf; var i,j,t:longint; begin assign(input,fi); reset(input); readln(m,n); re:=0; fillchar(a,sizeof(a),0); for i:=1 to m do begin for j:=1 to n do begin read(t); if t=0 then a[i,j]:=0 else begin a[i,j]:=a[i-1,j]+1; if a[i,j]>re then re:=a[i,j]; end; end; readln; end; close(input); end; procedure pr; var i,j,now,k,q,s:longint; begin if re=0 then exit; st[0]:=0; pos[0]:=0; for i:=1 to m do begin j:=1; now:=0; repeat if a[i,j]>0 then begin if a[i,j]>=st[now] then begin inc(now); st[now]:=a[i,j]; pos[now]:=j; end else begin k:=now; while (st[now]>a[i,j]) and (now>0) do dec(now); inc(now); for q:=k-1 downto now do begin s:=st[q]*(pos[k]-pos[q]+1); if s>re then re:=s; end; st[now]:=a[i,j]; inc(now); st[now]:=a[i,j]; pos[now]:=j; end; end else begin if a[i,j-1]>0 then begin for q:=now downto 1 do begin s:=st[q]*(j-pos[q]); if s>re then re:=s; end; now:=0; end; end; inc(j); until j>n+1; end; end; procedure wf; begin assign(output,fo); rewrite(output); write(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include<cstdio> const int N = 1005; /* Stack */ int stack[N], topS; void init() { topS = 0; } int top() { return stack[topS-1]; } int pop() { return stack[--topS]; } void push(const int &x) { stack[topS++] = x; } /* End of Stack */ int m, n, a[N][N], f[N][N], left[N], right[N]; /* f[y][x] = k <=> a[y..y+k-1][x] = 11..., k max */ void enter() { scanf("%d%d",&m,&n); for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) scanf("%d", &a[i][j]); } void calcF() { for(int j = 0; j < n; ++j) for(int i = m-1; i >= 0; --i) f[i][j] = a[i][j] ? f[i+1][j] + 1 : 0; } void maximize(int &a, const int &b) { if(a < b) a = b; } void solve() { int res = 0; for(int i = 0; i < m; ++i) { left[0] = 0; init(); for(int j = 1; j < n; ++j) if(f[i][j] > f[i][j-1]) left[j] = j, push(j-1); else { while(topS && f[i][j] <= f[i][top()]) pop(); left[j] = topS ? top() + 1 : 0; } right[n-1] = n-1; init(); for(int j = n-2; j >= 0; --j) if(f[i][j] > f[i][j+1]) right[j] = j, push(j+1); else { while(topS && f[i][j] <= f[i][top()]) pop(); right[j] = topS ? top() - 1 : n-1; } for(int j = 0; j < n; ++j) maximize(res, (right[j] - left[j] + 1) * f[i][j]); } printf("%d\n", res); } int main() { enter(); calcF(); solve(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N][N]; int h[N]; int c[N][N]; int n, m; struct Rectangle { int h, w; } s[N]; int size; int main() { ios::sync_with_stdio(false); cin >> m >> n; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j]; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) h[j] = a[i][j] ? h[j] + 1 : 0; for (int j = 0; j <= n + 1; ++j) { int w = 0; while (size > 0 && s[size].h >= h[j]) { int cur_h = max(s[size - 1].h, h[j]); w += s[size].w; ++c[cur_h + 1][w]; --c[s[size].h + 1][w]; --size; } ++size; s[size].w = w + 1; s[size].h = h[j]; } } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) c[i + 1][j] += c[i][j]; int c1 = 0, c2 = 0; for (int j = n; j >= 1; --j) { c1 += c[i][j]; c2 += c1; c[i][j] = c2; } } int ans = 0; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (c[i][j]) ans = max(ans, i * j); cout << ans << endl; return 0; }
Code mẫu của RR
uses math; var res,top,i,j,m,n:longint; a:array[1..1011,1..1011] of longint; down,left,right,stack:array[0..1011] of longint; begin read(m,n); for i:=1 to m do for j:=1 to n do read(a[i,j]); for i:=1 to m do begin for j:=1 to n do if a[i,j]=1 then down[j]:=down[j]+1 else down[j]:=0; top:=0; stack[0]:=0; for j:=1 to n do begin while (top>0) and (down[stack[top]]>=down[j]) do dec(top); left[j]:=stack[top]+1; inc(top); stack[top]:=j; end; top:=0; stack[0]:=n+1; for j:=n downto 1 do begin while (top>0) and (down[stack[top]]>=down[j]) do dec(top); right[j]:=stack[top]-1; inc(top); stack[top]:=j; end; for j:=1 to n do res:=max(res,down[j]*(right[j]-left[j]+1)); end; writeln(res); end.
Code mẫu của hieult
#include<string> #include<vector> #include<sstream> #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<queue> //#include<conio.h> using namespace std; #define FOR(i, a, b) for(int i=(a), _b=(b); i < _b; ++i) #define FORU(i, a, b) for(int i=(a), _b=(b); i <= _b; ++i) #define FORD(i, a, b) for(int i=(a), _b=(b); i >= _b; --i) #define maxn 1111 int l[2][maxn], r[2][maxn], h[2][maxn], a[maxn][maxn]; int main(){ //freopen("QBRECT.in","r",stdin); int m,n,kq = 0; scanf("%d %d",&m,&n); FORU(i, 1, m) FORU(j, 1, n) scanf("%d",&a[i][j]); memset(h,0,sizeof(h)); FORU(i, 1, m) FOR(t, 1, 2){ FORU(j, 1, n) { if(a[i][j]==t) h[t][j]++; else h[t][j] = 0; } h[t][0] = -1; h[t][n+1] = -1; FORU(j, 1, n){ l[t][j] = j; while(h[t][l[t][j]-1]>=h[t][j]) l[t][j] = l[t][l[t][j]-1]; } FORD(j, n, 1){ r[t][j] = j; while(h[t][r[t][j]+1]>=h[t][j]) r[t][j] = r[t][r[t][j]+1]; } FORU(j, 1, n){ kq = max(kq,h[t][j]*(r[t][j]-l[t][j]+1)); } } printf("%d",kq); //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} program QBRECT; const input = ''; output = ''; maxn = 1000; var s: array[1..maxn,1..maxn] of integer; stack,a,left,right: array[0..maxn] of integer; top,n,m,res: integer; procedure init; var f: text; i,j: integer; begin assign(f, input); reset(f); readln(f, m, n); for i := 1 to m do for j := 1 to n do read(f, s[i,j]); close(f); end; procedure push(v: integer); begin inc(top); stack[top] := v; end; procedure calc; var i: integer; begin top := 0; for i := 1 to n do begin while (top > 0) and (a[stack[top]] >= a[i]) do dec(top); if top = 0 then left[i] := 1 else left[i] := stack[top] + 1; push(i); end; top := 0; for i := n downto 1 do begin while (top > 0) and (a[stack[top]] >= a[i]) do dec(top); if top = 0 then right[i] := n else right[i] := stack[top] - 1; push(i); end; for i := 1 to n do if res < (right[i] - left[i] + 1) * a[i] then res := (right[i] - left[i] + 1) * a[i]; end; procedure solve; var i,j: integer; begin res := 0; fillchar(a, sizeof(a), 0); for i := 1 to m do begin for j := 1 to n do if s[i,j] = 1 then inc(a[j]) else a[j] := 0; calc; end; end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, res); close(f); end; begin init; solve; printresult; end.
Code mẫu của skyvn97
#include<stdio.h> #define MAX 1111 int a[MAX][MAX]; int h[MAX][MAX]; int stack[MAX]; int l[MAX]; int r[MAX]; int max,m,n; int size; void init(void) { scanf("%d",&m); scanf("%d",&n); int i,j; for (i=1;i<=n;i=i+1) h[0][i]=0; for (i=1;i<=m;i=i+1) for (j=1;j<=n;j=j+1) { scanf("%d",&a[i][j]); if (a[i][j]==0) h[i][j]=0; else h[i][j]=h[i-1][j]+1; } max=0; } void process(void) { int i,j,tmp; for (i=1;i<=m;i=i+1) { size=0; l[1]=1; for (j=2;j<=n;j=j+1) { if (h[i][j]>h[i][j-1]) { l[j]=j; size++; stack[size]=j-1; } else { while ((size>0) && (h[i][stack[size]]>=h[i][j])) size--; if (size==0) l[j]=1; else l[j]=stack[size]+1; } } size=0; r[n]=n; for (j=n-1;j>=1;j=j-1) { if (h[i][j]>h[i][j+1]) { r[j]=j; size++; stack[size]=j+1; } else { while ((size>0) && (h[i][stack[size]]>=h[i][j])) size--; if (size==0) r[j]=n; else r[j]=stack[size]-1; } } tmp=0; for (j=1;j<=n;j=j+1) if (tmp<h[i][j]*(r[j]-l[j]+1)) tmp=h[i][j]*(r[j]-l[j]+1); if (max<tmp) max=tmp; } printf("%d",max); } int main(void) { init(); process(); }
Code mẫu của khuc_tuan
#include <stdio.h> int m, n; int h[1000], l[1000], r[1000]; int main() { int i, j, xx, t, result = 0; scanf("%d%d", &m, &n); for(i=0;i<m;++i) { for(j=0;j<n;++j) { scanf("%d", &xx); h[j] = (xx==1) ? h[j]+1 : 0; } for(j=0;j<n;++j) { t = j-1; while(t>=0 && h[t]>=h[j]) t = l[t]; l[j] = t; } for(j=n-1;j>=0;--j) { t = j+1; while(t<n && h[t]>=h[j]) t = r[t]; r[j] = t; result >?= h[j] * (r[j]-l[j]-1); } } printf("%d\n", result); return 0; }
Bình luận