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

WA了好久,好心人看看,用栈做的

Posted by bluesmall at 2010-05-26 17:01:33 on Problem 2559
#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:
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