TIOJ 1063 最大矩形(Area) ( 95北市賽 prob 5 )

poao899    -8K    120MS    G++     0.75K     2009-11-10 22:18:00                                .

沒有一次AC真慚愧QQ

枚舉底 Stack 合計O(n^2)


//***************************

//95 prob5

#include<stdio.h>
int stack[202][2],top;
int rec[201];
int n,m;
int max;
main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        top=stack[0][0]=stack[0][1]=0;
        for(int j=1;j<=m;j++){
            char c=getchar();
            while(c==32||c==10)c=getchar();
            if(c=='0')rec[j]=0;
            else if(c=='1')rec[j]++;
            int startPop=j;
            while(rec[j]<stack[top][0]){
                max>?=(j-stack[top][1])*stack[top][0];
                startPop<?=stack[top][1];
                top--;
            }
            if(stack[top][0]!=rec[j]){
                top++;
                stack[top][0]=rec[j];
                stack[top][1]=startPop;
            }
        }
        while(~top){
            max>?=(m-stack[top][1]+1)*stack[top][0];
            top--;
        }
    }
    printf("%d\n",max);
}