dp单调队列优化

$dp[i]=\max/\min(dp[j])+c[i]$

dp 单调队列

for example: $dp[i]=\min(dp[j])+c[i]$考虑两个决策$p,q(p<q)$，若$dp[p]>=dp[q]$,则决策永远不可能为$p$。这是因为$dp[p]$的值没有$dp[q]$优，同时比$q$离开决策范围更快。总之，$q$的生存能力更强。

简单来讲，维护单调递增的一组决策

template <typename T>
struct dequeue
{
    vector <T> q;
    ll l,r;
    void init(int n)
    {
        q.resize(n);
        l=0,r=0;
    }
    bool empty()
    {
        return l>=r;
    }
    T back()
    {
        return q[r];
    }
    T front()
    {
        return q[l];
    }
    void pop_front()
    {
        l++;
    }
    void pop_back()
    {
        r--;
    }
    void push_back(T k)
    {
        q[++r]=k;
    }
    void insert(T k)
    {
        while (l<=r&&back().first<=k.first) pop_back();
        push_back(k);
    }
};

定义：

dequeue<pair<ll,int> > q;
q.init(101001);
for (ll i=1;i<=n;i++)
    {
        q.insert(make_pair(a[i],i));
        while (q.front().second<i-k+1) q.pop_front();
        if (i-k+1>0)
        {
            ans+=q.front().first;
        }
    }