Description：

给 $n$ 个数，求一个权值和最大的子序列满足任意一段长度都不超过 $k$ 。

$1\leqslant n\leqslant 10^5$

Solution：

肯定是 $DP$ ，方程为 $f[i]=\max(f[j-1]+sum[i]-sum[j])(i-j\leqslant k)$ ，化一下就是 $f[i]=sum[i]+\max(f[j-1]-sum[j])(i-k\leqslant j<i)$ ，于是这是一个滑动窗口区间极值可以用单调队列。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 100010

typedef long long ll;

ll a[MAXN],sum[MAXN];

int q[MAXN],head,tail;

ll F[MAXN],*f = F + 1;

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + a[i];

	head = 1;tail = 0;q[++tail] = 0;

	ll ans = 0;

	for(int i = 1;i <= n;++i)

	{

		while(head <= tail && q[head] < i - k)++head;

		f[i] = f[q[head] - 1] + sum[i] - sum[q[head]];

		while(head <= tail && f[q[tail] - 1] - sum[q[tail]] <= f[i - 1] - sum[i])--tail;

		q[++tail] = i;

		ans = max(ans,f[i]);

	}

	cout << ans << endl;

	return 0;

}