Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

改单调栈为什么re了呀

Posted by qq2567722641 at 2019-10-02 14:47:57 on Problem 3494
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator