P1714，用单调队列切最大的蛋糕

king_xbz · 2020-01-26 22:04:55 · 题解

这是一道考察单调队列优化dp的好题。

首先我们先来看题目：

小Z作为寿星，自然希望吃到的第一块蛋糕的幸运值总和最大

我们可以考虑用一维前缀和来进行预处理 即：

    for(fint i=1;i<=n;i++)
        a[i]=read();
    for(fint i=1;i<=n;i++)
        s[i]=s[i-1]+a[i];

接下来，我们接着往下看，

但小Z最多又只能吃M小块(M≤N)的蛋糕。

这可怎么办呢，难道需要暴力枚举每一个搭配吗？再看数据范围：

对20%的数据，N≤100。

对100%的数据，N≤500000，|Pi|≤500。 答案保证在2^31-1之内。

数据范围在int_max附近，所以我们想ac显然需要别的方法。

这时候，我们今天的主角----单调队列就要隆重登场了！

那么神马是单调队列呢？

我们可以把单调队列想象成一个长度为m的滑动窗口，在不停的滑动中所包含的值也不一样，而单调队列同时又满足单调性，即单调递增或单调递减（数学必修一）。

所以我们可以用两头均可出入的特殊数据结构————双向队列，来帮助我们实现。

code

    head[0]=head[1]=1;
    for(fint i=1;i<=n;i++)
    {
        while(!q.empty()&&q.back().cnt>=a[i].cnt)
        q.pop_back();
        q.push_back(a[i]);
        while(!s.empty()&&s.back().cnt<=a[i].cnt)
        s.pop_back();
        s.push_back(a[i]);
        if(i-head[0]>=k)
        {
        head[0]++;
        if(i-k==q.front().num)
        q.pop_front();
        }
        if(i-head[1]>=k)
        {
        head[1]++;
        if(i-k==s.front().num)
        s.pop_front();
        }
        if(i>=k)
        {
        v[i]=q.front().cnt;
        w[i]=s.front().cnt;
        }
    }

s中储存的即为减队列，q中储存的即为加队列。

类比到这道题，我们一样可以用单调队列来优化：

    int head=1;
    int maxxs=-inf;
    for(fint i=1;i<=n;i++)
    {
        while(!q.empty()&&s[q.back()]>=s[i])
        q.pop_back();
        q.push_back(i);
        if(q.front()<i-k)
            q.pop_front();
        maxxs=max(maxxs,s[i]-s[q.front()]);
    }

这便是使用单调队列和前缀和处理后的“蛋糕”。

最后，推荐几道相关题目：P1886单调队列模板题P2627修剪草坪

就到这里了，谢谢大家！