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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.