題目描述
媽媽成功將小竹救了出來，她覺得小竹實在是太笨了，決定關小竹一周禁閉。可是小竹哪里能忍受失去自由，他早就偷藏了一部手機用于聯系你，請求你幫助他逃離。

你通過觀察發現他房間內有 $n$ 個可用于制成繩子的物品，第 $i$ 個的長度為 $a_i$ 。當你使用第 $i$ 個物品制作繩子時，其右側的 $k$ 個物品（不含第$i$個物品）就無法再被用于制作繩子 。最終，小竹用選擇的物品制成繩子，繩子的長度是所選擇物品的長度之和。

小竹想知道,他能制作的繩子長度最長為多少？

輸入描述:
第一行兩個整數 $n,k(1\le k\le n\le 2000)$。
第二行 $n$ 個用空格隔開的整數，第 $i$ 個整數為 $(1\le a_i?\le 2000)$，表示第 $i$ 個物品的長度。

輸出描述:
一行一個整數，表示繩子的最長長度。

輸入

5 2
1 2 3 4 5

輸出

7

說明
使用第 $2$ 個和第 $5$ 個物品制成繩子

---

賽時壓根沒看出來是一個dp問題。

對于此問題，使用$f[i]$來代表從前$i$個里面選，這時候需要先分為兩種情況，第一種情況是第$i$個物品前面有$k$個物品，也就是$i?k?1>=0$，這時候我們就可以把集合劃分為選第$i$個還是不選第$i$個，如果選第$i$個，就是$f[i?k?1]+a[i]$，如果不選第$i$個，就是$f[i?1]$，第二種情況是前$i$個物品不夠$k$個物品，這時如果選第$i$個，就是 $a[i]$ ，如果不選第$i$個，就是$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;
}