-
Largest Submatrix of All 1’s
POJ题目链接:http://poj.org/problem?id=3494
单调栈水题,,,复习一下单调栈
求1组成的最大的矩阵,利用单调栈性质求出每个点的左右边界。
//#include <bits/stdc++.h> #include<map> #include<set> #include<queue> #include<cmath> #include<stack> #include<ctime> #include<cstdio> #include<vector> #include<string> #include<sstream> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=1e5+10; #define pi acos(-1.0) #define INF 0x3f3f3f3f #define mod 1000000009 #define endll printf("\n") #define s1(a) scanf("%d",&a) #define s2(a,b) scanf("%d %d",&a,&b) #define mem(a,b) memset(a,b,sizeof(a)) #define s3(a,b,c) scanf("%d %d %d",&a,&b,&c) int l[2222]; int s[2222]; int h[2222][2222]; int main() { int n,m; while(~s2(n,m)) { mem(h,0); //init for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int s;s1(s); h[i][j]=s?h[i-1][j]+1:0; } } // int ans=0; for(int i=1;i<=n;i++) { h[i][m+1]=-1; int top=0; //对每一行维护一个单调递增栈 //每个让某点出栈的元素即是此点的右边界 //让某点停止出栈的元素即是此点的左边界 for(int j=1;j<=m+1;j++)// { l[j]=j; while(top>0&&h[i][s[top]]>h[i][j]) { ans=max(ans,h[i][s[top]]*(j-l[s[top]])); l[j]=l[s[top]]; top--; } if(top>0&&h[i][s[top]]==h[i][j])//特判 l[j]=l[s[top]]; s[++top]=j; } } printf("%d\n",ans); } return 0; }