Lightoj1083【单调栈】

#include <cstdio>

#include <stack>

#include <iostream>

#include <string.h>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N=5e4+10;

struct asd

{

    LL pre;

    LL next;

    LL num;

};

int n;

LL ww[N];

int main()

{

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(int i=1; i<=n; i++)

            scanf("%lld",&ww[i]);

        stack<asd>q;

        asd tmp;

        tmp.num=ww[1];

        tmp.next=tmp.pre=1;

        q.push(tmp);

        LL ans=0;

        for(int i=2; i<=n; i++)

        {

            asd tmp1;

            tmp1.num=ww[i];

            tmp1.pre=tmp1.next=1;

            while(!q.empty()&&tmp1.num<q.top().num)

            {

                tmp=q.top();

                q.pop();

                tmp1.pre+=tmp.pre;

                if(!q.empty())

                    q.top().next+=tmp.next;

                ans=max(tmp.num*(tmp.pre+tmp.next-1),ans);

            }

            q.push(tmp1);

        }

        while(!q.empty())

        {

            tmp=q.top();

            q.pop();

            if(!q.empty())

                q.top().next+=tmp.next;

            ans=max(ans,(tmp.next+tmp.pre-1)*tmp.num);

        }

        printf("Case %d: %lld\n",cas++,ans);

    }

    return 0;

}
巴特西

Lightoj1083【单调栈】

最新文章

热门文章
