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; }