Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
改单调栈为什么re了呀#include<iostream> #include<cstring> using namespace std; const int maxn=2000+20; int a[maxn][maxn],w[maxn]; struct Stack{ int top; int data[maxn]; Stack(){top=-1;} bool empty(){return top==-1;} }; int ans; void push(Stack *stack,int x){ if(stack->empty()||x>stack->data[stack->top]){ stack->data[++stack->top]=x; w[stack->top]=1; }else{ int wid=0; while(!stack->empty()&&x<=stack->data[stack->top]){ wid+=w[stack->top]; ans=max(ans,wid*stack->data[stack->top]); stack->top--; } stack->data[++stack->top]=x; w[stack->top]=wid+1; } } int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF){ ans=0; memset(w,0,sizeof(w)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&a[i][j]); } } int k,k1; for(int i=0;i<n;i++){ int cnt=1; for(int j=0;j<n;j++){ if(a[j][i]==1){ a[j][i]=cnt++; }else if(a[j][i]==0){ cnt=1; } if(cnt>k){ k=cnt;k1=j; } } } Stack *stack=new Stack(); for(int i=0;i<n;i++){ push(stack,a[k1][i]); } push(stack,0); printf("%d\n",ans); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator