9度1497:最大面積の全1サブマトリクス(単調キュー、単調スタック)

2716 ワード

タイトルの説明:
1つのM*Nの行列の中で、すべての要素は0と1だけで、この行列の中から1つの面積の最大の全1サブ行列を探し出して、いわゆる最大は要素1の個数が最も多いことを指します.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力される最初の行は2つの整数m、n(1<=m、n<=1000):入力するマトリクスのサイズを表します.行列にはm行があり、各行にはn個の整数があり、それぞれ0または1であり、隣接する2つの数の間に厳密に1つのスペースで区切られている.
出力:
各テストケースに対応して、出力マトリクスの中で面積が最も大きい全1サブマトリクスの要素数.
サンプル入力:

サンプル出力:

4
構想:以前のzjnu 1735と差は多くないが、ここで求めたのは最大面積であり、q[][0]で高さを表し、q[][1]で下付きを表すとよい.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef long double ldb;
#define inf 99999999
#define pi acos(-1.0)
#define maxn 1005
int gra[maxn][maxn];
int h[maxn][maxn],l[maxn],r[maxn];
int q[111111][2];


int main()
{
    int n,m,i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(h,0,sizeof(h));
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                scanf("%d",&gra[i][j]);
                if(gra[i][j]==0)h[i][j]=0;
                else{
                    h[i][j]=1;
                    if(i>1){
                        h[i][j]+=h[i-1][j];
                    }
                }
            }
        }

        int front,rear;
        int maxx=0;
        for(i=1;i<=n;i++){
            front=1;rear=0;
            for(j=1;j<=m;j++){
                while(front<=rear && q[rear][0]>=h[i][j]){
                    rear--;
                }
                if(rear==0){
                    l[j]=1;
                }
                else{
                    l[j]=q[rear][1]+1;
                }
                rear++;
                q[rear][0]=h[i][j];
                q[rear][1]=j;
            }
            front=1;rear=0;
            for(j=m;j>=1;j--){
                while(front<=rear && q[rear][0]>=h[i][j]){
                    rear--;
                }
                if(rear==0){
                    r[j]=m;
                }
                else{
                    r[j]=q[rear][1]-1;
                }
                maxx=max(maxx,h[i][j]*(r[j]-l[j]+1) );
                rear++;
                q[rear][0]=h[i][j];
                q[rear][1]=j;
            }
        }
        printf("%d
",maxx);
    }
    return 0;
}

転載先:https://www.cnblogs.com/herumw/p/9464505.html

HDU 2030漢字統計(水~)

[快速キャンパスFE MGS 3期]-5日目