萌新刚学单调队列优化 DP ，发一篇题解纪念一下qwq

自认为详细的讲解

---

看到题目，是一个纯的选数问题，所以考虑用 DP 解。学过 DP 的都知道 DP 有三要素，所以我们先把这三个填完。

1. 阶段，这个其实一般来说就是循环的东西，比较好填，看题目可知是每个数的位置（编号）
2. 决策，对于每个数，我们当然有两种决策，即取和不取。

接下来是比较难的（虽然这题简单）状态（状态转移方程）了，这个需要根据决策来填，可以容易的写下下面的方程：

设\(f_{i,0}\)表示不取第\(i\)个数得到的最大结果，则有方程\(f_{i,0}=\max(f_{i-1,0},f_{i-1,1})\)

设\(f_{i,1}\)表示不取第\(i\)个数得到的最大结果，则有方程\(f_{i,1}=\max(f_{x,0}-s_x)+s_i\)（前提是\(i-k\leq x < i\)）

然而时间复杂度是\(O(n^2)\)，会 T ，所以我们要进行优化。

发现\(f_{x,0}-s_x\)随着的\(x\)的变化而变化，和\(i\)无关。并且因为他们是递增的，所以我们用\(f_{x,0}-s_x\)构造单调队列，把时间复杂度降到\(O(n)\)。

接下来就简单了，而且这一题也不用像模板写两头维护，只需要写一边就行，所以在循环内写上方程，敲一个单调队列外加上面的限制条件就行了。

AC code:

#include<bits/stdc++.h>
using namespace std;
long long n,m,l,r,x,s[100010],f[100010][10],q[100010];//这里要注意开longlong
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%lld",&x),s[i]=s[i-1]+x;//求前缀和
	l=r=1;
	for(int i=1;i<=n;i++)
	{
		f[i][0]=max(f[i-1][0],f[i-1][1]);//方程
		while(q[l]<i-m&&l<=r) l++;//维护队首
		f[i][1]=f[q[l]][0]-s[q[l]]+s[i];//方程
		while(f[i][0]-s[i]>f[q[r]][0]-s[q[r]]) r--;//维护队尾
		r++;q[r]=i; 
	}
	cout<<max(f[n][0],f[n][1]); //最后不要忘了再比较
	return 0; 
 } 

码字不易，给个赞呗qwq~~