DP问题

题目链接

题目描述：

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

你通过观察发现他房间内有 \(n\) 个可用于制成绳子的物品，第 \(i\) 个的长度为 \(a_i\)
。当你使用第 \(i\) 个物品制作绳子时，其右侧的 \(k\) 个物品（不含第\(i\)个物品）就无法再被用于制作绳子 。最终，小竹用选择的物品制成绳子，绳子的长度是所选择物品的长度之和。

小竹想知道,他能制作的绳子长度最长为多少？

输入描述：

\(第一行两个整数 n,k(1 \leq k\le n \le 2000)n,k(1≤k≤n≤2000)。\)

\(第二行 n 个用空格隔开的整数，第 i 个整数为 a_i(1 \le a_i \le 2000),表示第 i 个物品的长度。\)

输出描述：

一行一个整数，表示绳子的最长长度。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 2010;

int n, k;
int a[N];
int f[N]; // f[i] 表示1 - i 中绳子长度最大值

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++)
    {
        if (i <= k + 1) // 在 i 小于等于 k + 1时，只能选一种物品，且必须选择最大的
            f[i] = max(f[i - 1], a[i]);
        else
            f[i] = max(f[i - k - 1] + a[i], f[i - 1]); // f[i] 状态计算有两种类型，一种为选择第 i 个物品，另一种则为不选择第 i 个物品，两种情况取最大值
    }

    cout << f[n];

    return 0;
}