题目描述
妈妈成功将小竹救了出来，她觉得小竹实在是太笨了，决定关小竹一周禁闭。可是小竹哪里能忍受失去*，他早就偷藏了一部手机用于联系你，请求你帮助他逃离。
你通过观察发现他房间内有 n n n 个可用于制成绳子的物品，第 i i i 个的长度为 a i a_i ai 。当你使用第 i i i 个物品制作绳子时，其右侧的 k k k 个物品（不含第 i i i个物品）就无法再被用于制作绳子 。最终，小竹用选择的物品制成绳子，绳子的长度是所选择物品的长度之和。
小竹想知道,他能制作的绳子长度最长为多少？
输入描述:
第一行两个整数
n
,
k
(
1
≤
k
≤
n
≤
2000
)
n,k(1≤k≤n≤2000)
n,k(1≤k≤n≤2000)。
第二行
n
n
n 个用空格隔开的整数，第
i
i
i 个整数为
(
1
≤
a
i
≤
2000
)
(1≤a_i ≤2000)
(1≤ai≤2000)，表示第
i
i
i 个物品的长度。
输出描述:
一行一个整数，表示绳子的最长长度。
输入
5 2
1 2 3 4 5
输出
7
说明
使用第
2
2
2 个和第
5
5
5 个物品制成绳子
赛时压根没看出来是一个dp问题。
对于此问题，使用 f [ i ] f[i] f[i]来代表从前 i i i个里面选，这时候需要先分为两种情况，第一种情况是第 i i i个物品前面有 k k k个物品，也就是 i − k − 1 > = 0 i-k-1 >= 0 i−k−1>=0，这时候我们就可以把集合划分为选第 i i i个还是不选第 i i i个，如果选第 i i i个，就是 f [ i − k − 1 ] + a [ i ] f[i-k-1] + a[i] f[i−k−1]+a[i]，如果不选第 i i i个，就是 f [ i − 1 ] f[i-1] f[i−1]，第二种情况是前 i i i个物品不够 k k k个物品，这时如果选第 i i i个，就是 a [ i ] a[i] a[i] ，如果不选第 i i i个，就是 f [ i − 1 ] f[i-1] f[i−1]。
代码：
#include<iostream>
using namespace std;
const int N = 2010;
int f[N];
int a[N];
int n,k;
int main(){
cin >> n >> k;
for(int i = 1;i <= n;i++)cin >> a[i];
int res = 0;
for(int i = 1;i <= n;i++){
if(i-k-1 >= 0)f[i] = max(f[i-1],f[i-k-1]+a[i]);
else f[i] = max(a[i],f[i-1]);
res = max(f[i],res);
}
cout << res;
return 0;
}