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 |
WA了好久,好心人看看,用栈做的#include <cstdio> int main(void) { __int64 h[100005],ans; int left[100005],stack[100005],id[100005],top,i,j,n;//如果开了两个 //left和right的话,会爆了,所以只开一个,另个加上去 while (scanf("%d",&n)&&n) { h[0]=h[n+1]=-1;//方便退栈 for ( i=1,ans=-1; i<=n; i++) scanf("%I64d",&h[i]); for ( i=2,stack[top=0]=h[1],id[top]=1; i<=n+1; i++) { j=top; while (top>=0&&h[i]<stack[top])//退栈 { left[id[top]]=j-top; top--; } stack[++top]=h[i]; id[top]=i; } for ( i=n-1,stack[top=0]=h[n],id[0]=n; i>=0; i--) { j=top; while (top>=0&&h[i]<stack[top]) { left[id[top]]+=j-top; top--; } stack[++top]=h[i]; id[top]=i; } for ( i=1; i<=n; i++) { __int64 t=h[i]*(left[i]+1); if (ans<t) ans=t; } printf("%I64d\n",ans); } return 0; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator