POJ 3494 Largest Submatrix of All 1’s

题意：
给你一个矩阵 全由0,1组成 让你找出其中由1组成的面积最大的矩形
题意非常简单 但让人无从下手
其实如果我们一行一行处理 将矩阵转换到 柱状图 就有想法了
eg

我的方法是直接把 terrible set 的方法拉过来用的 事实证明 效率还好

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

int row,col,ans,tw,temp,top;
int mat[2010][2010];

struct grid
{
    int wid,high;
    grid(int a=0,int b=1):high(a),wid(b){}
}st[2010];

void push(int h)
{
    tw=temp=0;
    while(top>0)
    {
        if(st[top].high>h)
        {
            tw+=st[top].wid;
            if((temp=tw*st[top].high)>ans)
                ans=temp;
            top--;
        }
        else break;
    }
    tw++;
    if((temp=tw*h)>ans) ans=temp;
    if(h)  st[++top]=grid(h,tw);
}

int main()
{
    while(scanf("%d%d",&row,&col)!=EOF)
    {
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
                scanf("%d",&mat[i][j]);
        for(int i=1; i<=col; i++)
            mat[0][i]=0;
        ans=0;
        for(int i=1; i<=row; i++)
        {
            top=0;
            for(int j=1; j<=col; j++)
                if(mat[i][j]) mat[i][j]+=mat[i-1][j];
            for(int j=1; j<=col; j++)
                push(mat[i][j]);
            tw=temp=0;
            while(top>0)
            {
                tw+=st[top].wid;
                if((temp=tw*st[top].high)>ans)
                    ans=temp;
                top--;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}