正经题解｜大盗杰瑞

题意解析

我们可以把所有楼层分为两类：

1. 「只能通过楼梯到达」的楼层
2. 「可以通过电梯到达」的楼层

定义 $f(i)$ 为到达楼层 $i$ 能够拿到的金币数量。

对于「只能通过楼梯到达」的楼层，那么 $f(i) = f(i - 1) + A_i$，这种情况比较简单。

对于「可以通过电梯到达」的楼层，除了 $f(i - 1) + A_i$ 外，我们还可以从之前含有电梯的楼层到达，即：$\max{f(j)} + A_i \ (j - 1 \vert K,\ 1 \le j \le N) $。这种情况我们似乎要遍历之前的所有「可以通过电梯」到达的楼层来求取 $\max{f(j)}$，但是事实上，我们可以使用一个变量 $\tt{preMax}$ 来维护 $\max{f(j)}$。
那么转移便转化为了 $f(i) = \max{(f(i - 1), \tt{preMax})} + A_i$。
这样这种情况下的状态转移也只需要 $\mathrm{O}(1)$ 的时间复杂度得到。

接下来我们看下如何处理 「有安保的楼层」。

对于「有安保的楼层」，我们可以将以上讨论的两种楼层合并，直接跳转到下一个「可以通过电梯到达」的楼层即可。即：当前楼层为 $i$，若 $A_i = -1$，则跳转到楼层 $(\lfloor \frac{i}{k} \rfloor + 1) \times K$。

这样我们便处理了所有情况，要注意的是，不一定到达最后一个楼层获得的金币是最多的，对于本题答案为 $\max{f(i)}$。

AC 代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (auto &x : a) cin >> x;
        vector<i64> dp(n + 1);
        dp[0] = a[0];
        i64 preMax = dp[0];
        int i = 1;
        while (i < n) {
            if (a[i] == -1) {
                i = (i / k + 1) * k;
                continue;
            }
            if (i % k == 0) {
                dp[i] = max(preMax, dp[i - 1]) + a[i];
                preMax = dp[i];
            }
            else {
                dp[i] = dp[i - 1] + a[i];
            }
            i++;
        }
        cout << *max_element(begin(dp), end(dp)) << '\n';
    }
    return 0;
}

复杂度分析

动态规划的状态数为 $N$ 个，转移的时间复杂度为 $\mathrm{O}(1)$，总的时间复杂度为 $\mathrm{O}(N)$。