题解

题意是，给定一个长度为 $n$ 的整数序列，需要从中选出一些位置，使得任意连续 $k$ 个位置中至少有一个被选中，求被选中位置上的数值之和的最大可能值。

由于最后一个被选中的位置不一定在序列末尾，但它必须位于最后 $k$ 个位置之内（否则最后 $k$ 个位置将没有元素被选中），因此最终答案需要在 $dp[n-k+1]$ 到 $dp[n]$ 中取最大值。

首先考虑经典的 DP ，定义 $dp[i]$ 为，考虑了前 $i$ 个数，且第 $i$ 个数必须被选中的情况下能获得的最大总和。为了方便处理边界，我们添加一个虚拟的第 $0$ 个位置，令 $dp[0] = 0$。

转移方程为 : $dp[i] = max(dp[i - j] + a[i], dp[i])$，其中 $j \in [1, k]$，此时的复杂度为 $O(nk)$ 并不能满足题目的要求。