HihoCoder1673 : 01间隔矩阵（[Offer收割]编程练习赛41）（单调队列）

描述

给定一个N × M的01矩阵，小Hi希望从中找到一个01间隔的子矩阵，并且子矩阵的面积越大越好。

例如对于

0101010

1000101

0101010

1010101

0101010

在右侧有一个5 × 4的01间隔子矩阵，在下方有一个3 × 7的01间隔子矩阵。

输入

第一行包含两个整数N和M。

以下N行M列包含一个N × M的01矩阵。

对于30%的数据，1 ≤ N, M ≤ 250

对于100%的数据，1 ≤ N, M ≤ 2000

输出

输出最大的01间隔子矩阵的面积。

样例输入

样例输出

模型：滑动窗口，最大广告牌面积
手段：单调队列

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

const int maxn=;

char c[maxn][maxn];

int H[maxn][maxn],L[maxn][maxn],R[maxn][maxn],n,m,i,j,ans=;;

int main()

{

    scanf("%d%d",&n,&m);

    for(i=;i<=n;i++) scanf("%s",c[i]+);

    for(i=;i<=m;i++) H[][i]=;                 //得到h

    for(i=;i<=m;i++)

      for(j=;j<=n;j++)

        H[j][i]=c[j][i]==c[j-][i]?:H[j-][i]+;

    for(i=;i<=n;i++)                            //得到相应h的左延伸

     for(j=;j<=m;j++){

         if(j==) { L[i][j]=;continue;}//边界处理

         int k=j;

         while(k>&&c[i][k]!=c[i][k-]&&H[i][k-]>=H[i][j]) k=L[i][k-];

         L[i][j]=k;

     }

    for(i=;i<=n;i++)                             //得到相应h的右延伸

     for(j=m;j>=;j--){

         if(j==m) {R[i][j]=m;continue;}

         int k=j;

         while(k&&k<m&&c[i][k]!=c[i][k+]&&H[i][k+]>=H[i][j]) k=R[i][k+];

         R[i][j]=k;

     } 

    for(i=;i<=n;i++)

     for(j=;j<=m;j++)

        if((R[i][j]-L[i][j]+)*H[i][j]>ans)  ans=(R[i][j]-L[i][j]+)*H[i][j];

    printf("%d\n",ans);

    return ;

}