Largest Submatrix of All 1’s--（单调队列）

Largest Submatrix of All 1’s

Time Limit : 10000/5000ms (Java/Other)   Memory Limit : 262144/131072K (Java/Other)

Total Submission(s) : 40   Accepted Submission(s) : 20

Problem Description

Given a m-by-n (0,1)-matrix, of all its submatrices of all 1’s which is the largest? By largest we mean that the submatrix has the most elements.

 

Input

<p>The input contains multiple test cases. Each test case begins with <i>m</i> and <i>n</i> (1 ≤ <i>m</i>, <i>n</i> ≤ 2000) on line. Then come the elements of a (0,1)-matrix in row-major order on <i>m</i> lines each with <i>n</i> numbers. The input ends once EOF is met.</p>

 

Output

<p>For each test case, output one line containing the number of elements of the largest submatrix of all 1’s. If the given matrix is of all 0’s, output 0.</p>

 

Sample Input

2 2 0 0 0 0 4 4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0

 

Sample Output

0 4

与之前题目：Largest Rectangle in a Histogram很像，题目是求最大矩形面积，与那题不同的的是，这题要以不同边为低分别求一次取最大值，题目先预处理使a[i][j]代表a[i][j]以及下面1的个数（相当于高度），然后对于a[i][j]再求出他左右比他连续高的列数（作为底）

代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
#define inf 0x7fffffff
int n,m,a[2005][2005],b[2005],q[2005],l[2005],r[2005];
ll work(int i)
{
    int j,tail=1; q[1]=0;
    for(j=1;j<=m;j++)
    {
        while(tail>=1&&a[i][q[tail]]>=a[i][j]) tail--;
        l[j]=j-q[tail]-1;
        q[++tail]=j;
    }
    tail=1; q[1]=n+1;
    for(j=m;j>=1;j--)
    {
        while(tail>=1&&a[i][q[tail]]>=a[i][j]) tail--;
        r[j]=q[tail]-1-j;
        q[++tail]=j;
    }
    ll maxn=0,temp=0;
    for(j=1;j<=m;j++)
    {
        temp=(l[j]+r[j]+1)*a[i][j];
        if(temp>maxn) maxn=temp;
    }
    return maxn;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        ll ans=0,temp;
        for(i=n-1;i>=1;i--)
            for(j=1;j<=m;j++)
                if(a[i][j]!=0) a[i][j]=a[i+1][j]+1;
        for(i=1;i<=n;i++)
        {
            temp=work(i);
            if(temp>ans) ans=temp;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}