題干：

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

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

Output

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.

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

題目大意：

? ? ? ? 求最大的子矩陣中數(shù)的和（其實(shí)也就是1的個(gè)數(shù)）

解題報(bào)告：

大佬說： ? 想起在學(xué)習(xí)dp時(shí)，曾經(jīng)遇到過矩形求最大n子段和問題，用的狀態(tài)壓縮，這里也可以用這個(gè)，把矩形壓縮成一條線，然后的過程，就是例題求矩形面積了，不過這里要求n遍，因?yàn)槊啃卸家獕嚎s，每行都要求一遍。于是這個(gè)題變得就簡(jiǎn)單多了。不過要注意的是最后需要枚舉每一行的狀態(tài)，而不能枚舉maze值最大那一行的狀態(tài)，（即：就算這一行的某一列是把這一列本該有的那個(gè)高度攔腰折斷，也要枚舉這一行）因?yàn)檎f不定在別的列的值大呢，而且，就算攔腰折斷了，這也算是一種狀態(tài)啊，所包含的所有狀態(tài)必須全部枚舉一遍，不重不漏，才能保證最終結(jié)果的正確性。

AC代碼：

#include<iostream> #include<cmath> #include<cstdio> #include<algorithm> #include<stack>using namespace std; const int MAX = 2000 + 5; int n,m; int maze[MAX][MAX]; int L[MAX],R[MAX];void getl(int i) {stack<int > sk;//要找他左側(cè)的第一個(gè)嚴(yán)格比他小的元素 所以需要從左向右維護(hù)一個(gè)嚴(yán)格單調(diào)遞增棧 for(int j = 1; j<=n; j++) {while(!sk.empty() && maze[i][sk.top() ]>=maze[i][j] ) sk.pop();if(sk.empty() ) L[j] = 0;else L[j] = sk.top();sk.push(j);}} void getr(int i) {stack<int > sk;//要找他右側(cè)的第一個(gè)嚴(yán)格比他小的元素 所以需要從右向左維護(hù)一個(gè)嚴(yán)格單調(diào)遞增棧 for(int j = n; j>=1; j--) {while(!sk.empty() && maze[i][sk.top() ]>=maze[i][j] ) sk.pop();if(sk.empty() ) R[j] = n+1;else R[j] = sk.top();sk.push(j);}} void init() {for(int i = 1; i<=m; i++)for(int j = 1; j<=n; j++)maze[i][j]=0; } int main() {while(~scanf("%d %d",&m,&n) ) {//m行n列 init();for(int i = 1; i<=m; i++) {for(int j = 1; j<=n; j++) {int tmp;scanf("%d",&tmp);if(tmp==1) {maze[i][j]=maze[i-1][j]+1;}}}//至此我們已經(jīng)有了截止第i行的(1~i)每一個(gè)j的連續(xù)高度， int maxx=-1;for(int i = 1; i<=m; i++) {getl(i);getr(i);//加入實(shí)時(shí)判斷，這樣就不用開二維的L[][]和R[][]了！！ // printf("i=%d 時(shí) ",i); for(int j = 1; j<=n; j++) { // printf("L[%d] =%d ",j,L[j]);maxx= max(maxx, maze[i][j] * (R[j] - L[j] -1) );} // printf("\n");}printf("%d\n",maxx);}return 0 ;}

總結(jié)： ?

? ?1.實(shí)時(shí)判斷！這樣就不用開一個(gè)二維數(shù)組了！最近很多題都用到了for循環(huán)中實(shí)時(shí)判斷實(shí)時(shí)操作的題！以后有空來一波總結(jié)。

? ?2. 適量的注釋有的時(shí)候真的讓人看著神清氣爽

總結(jié)

以上是生活随笔為你收集整理的【POJ - 3494】Largest Submatrix of All 1’s（加一点思维后化成 单调栈）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。