题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2442
考虑记录前 i 个、末尾 j 个连续选上的最大值。发现时空会爆。
又发现大量的转移形如 dp[ i ][ j ] = dp[ i-1 ][ j-1 ]+a[ i ]。
再结合自己求答案要遍历 j = i ~ j - k ，就觉得可以只记录一个 i ，在 i 到 i - k 的范围强制选后面连续的一段，并让转移来的dp的后面一个强制不选。
这样在 i 到 i-k 的范围里在强制选的后缀之前一定有一个不选的，符合条件。
实现需要一点技巧。
1.dp[i-1]表示 i-1 之后的那个格子不选。所以应该先fx+=a[i]，再dp[i-1]-=fx，这样dp[i-1]没有加上a[i]的值，符合设定。
2.如果从开始就一直选，岂不是要从dp[ -1 ]转移来才行？所以把所有角标+1，就行了！原来的dp[0]变成dp[1]，不用特殊管。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=1e5+;
int n,k,q[N];
ll a[N],dp[N],h,t,fx;
int rdn()
{
int ret=;char ch=getchar();
while(ch>''||ch<'')ch=getchar();
while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();
return ret;
}
ll rdl()
{
ll ret=;char ch=getchar();
while(ch>''||ch<'')ch=getchar();
while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();
return ret;
}
int main()
{
n=rdn();k=rdn();
h=;q[++t]=;
for(int i=;i<=n+;i++)
{
a[i]=rdl();
while(h<=t&&i-q[h]>k+)h++;
fx+=a[i];dp[i-]-=fx;
while(h<=t&&dp[i-]+fx>=dp[q[t]]+fx)t--;
q[++t]=i-;
dp[i]=dp[q[h]]+fx;
// printf("dp[%d]=%lld dp[%d]=%lld fx=%lld\n",i,dp[i],q[h],dp[q[h]],fx);
}
printf("%lld",dp[n+]);
return ;
}