题意
从数列$a$中选出若干数，但不能有超过$k$个连续的数字被选择，求选出数字的最大和
数据范围：$1 \le n \le 10^5,1 \le a_i \le 10^9$
题解
用$f[i]$表示选到第$i$个时的最大值，显然，在$j \in [i-k,i]$一定存在至少$1$个断点，否则存在超过$k$的连续段，所以枚举该断点
$$f[i]=max(f[j-1]+a[j+1]+ \dots +a[i])$$
将求和部分用前缀和优化
$$f[i]=max(f[j-1]+s[i]-s[j])$$
可将$s[i]$移出
$$f[i]=max(f[j-1]-s[j])+s[i]$$
此时取最大值只与$j$有关，考虑单调队列优化
代码：
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
const int N=100000+10;
int n,r;
int a[N],s[N],b[N],q[N];
int frt,bck=1;
int dp[N];
signed main(){
scanf("%lld%lld",&n,&r);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++){
b[i]=dp[i-1]-s[i];
for(;b[q[bck]]<b[i] && bck>=frt;bck--);
q[++bck]=i;
for(;i-q[frt]>r && bck>=frt;frt++);
dp[i]=b[q[frt]]+s[i];
}
printf("%lld",dp[n]);
return 0;
}