BaconToast 的跳棋寻宝

题目描述

在一个由 $n$ 个格子组成的一维序列中，每个格子上放有 $a_i$ 个金币。$\text{BaconToast}$ 从某一格子出发，每次中间间隔至少 $k$ 个格子向前方跳跃一次，并获得格子上的金币，求他能够获得的最大金币数是多少（包括最初位于的格子）？

输入

输入一行两个数 $n, k(n\leq 10^5, 1\leq k\leq100)$，意义同上描述。

接下来输入一行 $n$ 个数 $a_i$ ，表示按顺序每个格子上的金币数，保证所有 $a_i$ 相加不超过 int 范围。

输出

输出一个数，表示按照间隔 $k$ 取数的规则，能够获得的最大金币数。

输入样例

6 1
1 1 4 5 1 4

输出样例

10

BUG 代码

#include <stdio.h>
int main() {
    int a[100005], dp[100005] = {0}; // dp 表示只考虑前 i 个数且取第 i 个数的情况下，总和的最大值
    int n, k, maxdp = 0;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (i - k >= 0) {
            if (dp[i - k] > maxdp) {
                maxdp = dp[i - k];
            }
            dp[i] = maxdp + a[i];
        }
        else {
            maxdp = a[i];
        }
    }
    for (int i = 0; i < n; i++) {
        if (dp[i] > maxdp) {
            maxdp = dp[i];
        }
    }
    printf("%d", maxdp);
    return 0;
}

Author: $\text{BaconToast}$