[codevs1159]最大全零子矩阵

传送门←

先DP处理出每点向上最多扩展出的0的个数
再用二维单调栈处理最大矩形
其实就是对每一行跑一遍单调栈……

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int MAXN = 2000 + 50;
int map[MAXN][MAXN],f[MAXN][MAXN],dp[MAXN][MAXN];
int n,ans;
struct zt
{
    int h,l,w;
};
stack <zt> q;
void solve(int k)
{
    for(int i = 1;i <= n;i ++)
    {
        int h = dp[k][i];
        if(!q.empty())
        {
            zt u = q.top();
            zt p = u;
            if(u.h < h)
            {
                q.push((zt){h,i,i - p.l});//
                continue;
            }
            while(u.h >= h)
            {
                q.pop();
                ans = max(ans,max(u.h * (i - u.l + u.w - 1),h * (i - u.l + u.w)));//
                if(q.empty())
                {
                    ans = max(ans,h * (i - u.l + u.w));
                    break;
                }
                p = u;
                u = q.top();
            }
            q.push((zt){h,i,i - p.l + p.w});
        }
        else q.push((zt){h,i,1});
        ans = max(ans,h);
    }
    while(!q.empty())
    {
        zt u = q.top();
        q.pop();
        if(q.empty())
        {
            ans = max(ans,u.h * u.w);
            return;
        }
        zt x = q.top();
        ans = max(ans,x.h * (u.l - x.l + x.w));
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    for(int j = 1;j <= n;j ++)
        scanf("%d",&map[i][j]);
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++)
        dp[j][i] = !map[j][i] * (dp[j - 1][i] + 1);
    }
    for(int i = 1;i <= n;i ++)
    {
        solve(i);
    }
    printf("%d",ans);
}

tips:
1、明确宽度是否包括端点
2、宽度标志着该元素栈前元素实际位置→该元素位置，就是包括所有该元素前因不满足单调性而被弹出的元素宽度（栈为单调递增栈，故前面不满足弹出的元素一定是高度大了的，所以一定可以按照当前高度计算为矩形）；
3、思路要清楚……至少要想清楚自己在打什么……OTZ