牛客小白月赛60 C 小竹关禁闭(动态规划 01背包)

题目描述
妈妈成功将小竹救了出来，她觉得小竹实在是太笨了，决定关小竹一周禁闭。可是小竹哪里能忍受失去自由，他早就偷藏了一部手机用于联系你，请求你帮助他逃离。

你通过观察发现他房间内有 $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
1
2

输出

7
1

说明
使用第 $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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19