题解 P2422 【良好的感觉】

xMinh · 2018-01-20 21:46:16 · 题解

luogu2422 良好的感觉

其实我是来推自己的新博客的

这题说实话想了我差不多一个小时。第一次没看题解用单调队列来优化DP。

这个题的单调队列很明显是一个没有时间限制的，所以只需要考虑队中元素是什么的问题。我们可以注意到，这个题的数据范围规定没有负数，所以前缀和绝对是会越来越大的，所以队中元素应该是那个最不舒服的值。

然后转念想一想，如果这题是一个数据小的普通DP怎么做？那就是找到每个点左边那个比它小的，以及右边那个比它小的。这左右边界之间的，就是这个点最多能管到的范围。对于单调队列来说，我们可以维护一个单调递增的队列，然后往外踢的时候，被踢掉的点就找到了“右边那个比它小的”，维护完队列之后，队列中位于当前元素前一个的那个元素就是“左边那个比它小的”。这样就可以计算某个点能管到的范围了，最后再乘以这个点本身的值，比较出最大值就好了。

当然还有一个问题，如果某个点一直没有被踢掉怎么办？好办，在序列的最后加一个值为0的元素，就可以在最后一次循环踢掉所有队中元素，完成最后的处理。

PS：其实这题的数据结构严格来说叫做单调栈。

#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
using namespace std;
long long n,a[100001],q[100001],sum[100001],f[100001],ans,tail;
int main()
{
    scanf("%lld",&n);
    for (rint i=1;i<=n;i++) scanf("%lld",&a[i]);
    n++;a[n]=0;
    for (rint i=1;i<=n;i++) 
    {
        sum[i]=sum[i-1]+a[i];
        while (a[q[tail]]>a[i])
        {
            f[q[tail]]+=(sum[i-1]-sum[q[tail]]);
            tail--;
        }
        f[i]=sum[i]-sum[q[tail]];
        q[++tail]=i;
    }
    for (rint i=1;i<=n-1;i++) ans=max(ans,f[i]*a[i]);
    printf("%lld",ans);
}