POJ 3494 Largest Submatrix of All 1’s（单调栈）

单调栈
题目意思：
有一个 0 和 1 数字构成的矩阵，要求全是数字1构成的子矩阵的最大面积。
题目类似于 POJ 2559。
本题要点：
1、算法竞赛进阶指南，54页，单调栈算法，依次扫描每一行即可。
2、用数组 h[i][j]记录每一行的某一列对应大高度。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 2010;
int h[MaxN][MaxN];
int matr[MaxN][MaxN];
int n, m, ans;
int s[MaxN], w[MaxN];void Monotonous_stack(int k)	//第k行
{
    h[k][m + 1] = 0;int p = 0;for(int i = 1; i <= m + 1; ++i)	{
    if(h[k][i] >= s[p]){
    s[++p] = h[k][i], w[p] = 1;}else{
    int width = 0;while(s[p] > h[k][i]){
    width += w[p];ans = max(ans, width * s[p]);--p;}s[++p] = h[k][i], w[p] = width + 1;}}
// printf("k = %d, ans = %d\n", k, ans);
}void sovle()
{
    for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= m; ++j){
    if(matr[i][j] == 0){
    h[i][j] = 0;}else{
    h[i][j] = 1 + h[i - 1][j];}
// printf("h[%d][%d] = %d\n", i, j, h[i][j]);}}ans = 0;for(int k = 1; k <= n; ++k){
    Monotonous_stack(k);}printf("%d\n", ans);
}int main()
{
    while(scanf("%d%d", &n, &m) != EOF){
    for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= m; ++j){
    scanf("%d", &matr[i][j]);}}sovle();}return 0;
}/* 2 2 0 0 0 0 4 4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 *//* 0 4 */