dp单调队列优化

dp单调队列优化

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

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;
    	}
    }