【dp+单调队列优化】选择数字

传送鸡：CodeVS3327

---

用$f_i$表示前i个数中的最大数字和，$pre_i$表示前i个数的前缀和，那么：

$$f_i=max(f_{j-1}+pre_i-pre_j | i-k\leqslant j\leqslant i)$$

其中j枚举的是第j个不选，防止连加个数超过k

可以发现这个式子其实只与j有关（i是枚举的）

于是建一个关于$(f_{j-1}+pre_j)$的单调队列优化转移即可

---

代码好短：

#include<iostream>
#include<cstdio>

using namespace std;

#define LL long long

LL n,m,t,w,ans,a[100030],pre[100030],f[100030],q[100030][3];

int main(){
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		pre[i]=pre[i-1]+a[i];
	}
	
	t=w=1;
	for (int i=1;i<=n;i++){
		while (f[i-1]-pre[i]>=q[w][1]) w--;
		q[++w][1]=f[i-1]-pre[i]; q[w][2]=i;
		while (q[t][2]<i-m) t++;
		f[i]=q[t][1]+pre[i];
		if (f[i]>ans) ans=f[i];
	}
	
	printf("%lld\n",ans);
	
	return 0;
}