【CF940E】Cashback（单调队列dp）

传送门

Solution:

既然是删掉k/c个，那么k<c是不删除的无意义，k=c删除1个，c<=k<2c还是删除1个，那么相当于第c+1个到第k个放在上一区间是无意义的。证明：假如前c个的最小值是mini ，如果

a[c+1]<mini，那么删掉的就是a[c+1]，不值得，如果a[c+1]>=mini，那么删除的还是mini，把c+1个划分到上个区间也是无意义的。

但如果长度为2c的话就能删除2个，但一定不如化成2个c长度的区间优秀。假如前c个的最小值是mini1，次小值是mini2，后c个的最小值是mini3，假如mini2<mini3，那么删除

mini1+mini3>mini1+mini2，划分成2段更好，如果mini2>=mini3，那么删除的还是mini1+mini3，是等价的。

这样我们就能想到区间dp了，f[i]为到i位置能减去的最大的和是多少，可以从f[i-1]转移过来，就相当于把i分到一个长度不到c的区间里，无法减去值，也可以从f[i-c]转移过来，说明吧i-

c+1到i分成一个长度为c的区间，然后删掉里面的最小值

分析到这儿我们发现其实就是一个RMQ+dp 对于RMQ 这道题可以用单调队列来解决 当然 st表，线段树也是可以的

友情提示：用stl的deque会炸哦~

/*1、维护区间最值；
2、去除冗杂状态；
3、保持队列单调（最大值是单调递减序列，最小值是单调递增序列）；
4、最优选择在队首
                    */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,c;
ll a[100005],sum,b[100005],dp[100005];
ll q[100005];
int main()
{
    cin>>n>>c;
    c=min(c,n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    int head,tail;
    q[head=tail=1]=1;
    for(int i=2;i<=c-1;i++)
    {
        while(a[q[tail]]>=a[i]) {
            tail--; 
        }
        q[++tail]=i;
    }
    for(int i=c;i<=n;i++)
    {
        while(head<=tail&&q[head]<=i-c) head++;
        while(head<=tail&&a[q[tail]]>=a[i]) tail--;
        q[++tail]=i;
        b[i]=a[q[head]];            
    }
    for(int i=c;i<=n;i++) dp[i]=max(dp[i-1],dp[i-c]+b[i]);
    cout<<sum-dp[n];
    return 0;
}