【Luogu】P2422良好的感觉（单调栈）

　　题目链接

　　写代码能力需要极大提升。我在五分钟之内想到了单调栈，然后花了一个小时的时间去看我单调队列为啥写错了……

　　首先这题需要转换自己的思维。枚举所有“最小点”，然后看它往左往右最大能扩展多少。

　　维护一个单调递增的序列，弹栈时就会是这种情况：

　　设被弹出去的元素是s，那它为什么会被弹出去呢？因为它比当前元素大。

　　比当前元素大说明了什么呢？说明如果有一个区间以它为最小值，那这个区间向右扩展的极限就在当前元素前面。因为区间不能继续向右扩展，一扩展，区间就包含当前元素了，那元素s就不是最小值了，而我们这个区间又是以s为最小值的区间……

　　所以我们分析出了区间的右端点。区间的左端点在栈顶的下面一个元素停住。推理同上。

　　于是一个区间枚举成功。可以把这个区间的价值和当前答案比对并更新答案。

　　代码如下。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

long long ans;

long long sum[];

long long que[];

int d[],t;

int main(){

    int n;

    scanf("%d",&n);

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

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

        sum[i]=sum[i-]+que[i];

        while(t&&que[d[t]]>=que[i]){

            ans=max(ans,que[d[t]]*(sum[i-]-sum[d[t-]]));

            t--;

        }

        d[++t]=i;

    }

    while(t){

        ans=max(ans,que[d[t]]*(sum[n]-sum[d[t-]]));

        t--;

    }

    printf("%lld",ans);

    return ;

}

巴特西

【Luogu】P2422良好的感觉（单调栈）

最新文章

热门文章