Bakser's Blog

我是逗比。

bzoj1057 最大子矩阵

| Comments

还是单调栈悬线法维护最大子矩阵,正方形什么的求矩形时稍微带一下就可以了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 2010
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define sqr(a) (((a)*(a)))
struct hh
{
    int h,len;
}s[N];
int n,m,height[N][N],db,ans1,ans2,top;
bool map[N][N];
inline void build()
{
    memset(height,0,sizeof(height));
    for(int i(1);i<=n;i++)
    for(int j(1);j<=m;j++)
    if(map[i][j])
    height[i][j]=height[i-1][j]+1;
}
inline void push(int h)
{
    int len(0);
    while(top&&s[top].h>h)
    {
        len+=s[top].len;
        ans1=MAX(ans1,len*s[top].h);
        ans2=MAX(ans2,sqr(MIN(s[top].h,len)));
        top--;
    }
    s[++top].h=h;
    s[top].len=len+1;
}
inline void clear()
{
    int len(0);
    while(top)
    {
        len+=s[top].len;
        ans1=MAX(ans1,len*s[top].h);
        ans2=MAX(ans2,sqr(MIN(len,s[top].h)));
        top--;
    }
    s[top].h=s[top].len=0;
}
inline void deal()
{
    for(int i(1);i<=n;i++)
    {
        for(int j(1);j<=m;j++)
            push(height[i][j]);
        clear();
    }
}
int main()
{
    //freopen("test.txt","r",stdin);
 scanf("%d%d",&n,&m);
    for(int i(1);i<=n;i++)
    for(int j(1);j<=m;j++)
    {
        scanf("%d",&db);
        if(((i&1)==(j&1)&&db)||((i&1)!=(j&1)&&!db))map[i][j]=1;
        else map[i][j]=0;
    }
    build();
    deal();
    for(int i(1);i<=n;i++)
    for(int j(1);j<=m;j++)
    map[i][j]^=1;
    build();
    deal();
    printf("%d\n%d\n",ans2,ans1);
    return 0;
}

Comments

comments powered by Disqus