题意解析 我们可以把所有楼层分为两类： 1. 「只能通过楼梯到达」的楼层 2. 「可以通过电梯到达」的楼层 定义 f(i)f(i)f(i) 为到达楼层 iii 能够拿到的金币数量。 对于「只能通过楼梯到达」的楼层，那么 f(i)=f(i−1)+Aif(i) = f(i - 1) + A_if(i)=f(i−1)+Ai ，这种情况比较简单。 对于「可以通过电梯到达」的楼层，除了 f(i−1)+Aif(i - 1) + A_if(i−1)+Ai 外，我们还可以从之前含有电梯的楼层到达，即：$\max{f(j)} + A_i \ (j - 1 \vert K,\ 1 \le j \le N) $。这种情况我们似乎要遍历之前的所有「可以通过电梯」到达的楼层来求取 max⁡f(j)\max{f(j)}maxf(j)，但是事实上，我们可以使用一个变量 preMax\tt{preMax}preMax 来维护 max⁡f(j)\max{f(j)}maxf(j)。 那么转移便转化为了 f(i)=max⁡(f(i−1),preMax)+Aif(i) = \max{(f(i - 1), \tt{preMax})} + A_if(i)=max(f(i−1),preMax)+Ai 。 这样这种情况下的状态转移也只需要 O(1)\mathrm{O}(1)O(1) 的时间复杂度得到。 接下来我们看下如何处理 「有安保的楼层」。 对于「有安保的楼层」，我们可以将以上讨论的两种楼层合并，直接跳转到下一个「可以通过电梯到达」的楼层即可。即：当前楼层为 iii，若 Ai=−1A_i = -1Ai =−1，则跳转到楼层 (⌊ik⌋+1)×K(\lfloor \frac{i}{k} \rfloor + 1) \times K(⌊ki ⌋+1)×K。 这样我们便处理了所有情况，要注意的是，不一定到达最后一个楼层获得的金币是最多的，对于本题答案为 max⁡f(i)\max{f(i)}maxf(i)。 AC 代码 复杂度分析 动态规划的状态数为 NNN 个，转移的时间复杂度为 O(1)\mathrm{O}(1)O(1)，总的时间复杂度为 O(N)\mathrm{O}(N)O(N)。