| ||||||||||
| 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