这种表述的题一眼dp。若没有封印规则，那么设 fif_ifi 为考虑前 iii 层的最大价值， fi=fi−1+maxj=1j≤mvi,jf_i = f_{i-1}+max_{j=1}^{j \le m}v_{i,j}fi =fi−1 +maxj=1j≤m vi,j 。而有封印规则后，我们可以设 fi,1/2f_{i,1/2}fi,1/2 为考虑前 iii 层后第一或第二大的价值，同时用 gi,1/2g_{i,1/2}gi,1/2 表示 fi,1/2f_{i,1/2}fi,1/2 中对应的选择的列数。如果当前选择的列与 gi,1g_{i,1}gi,1 相同，则由于封印规则而不能选择 fi,1f_{i,1}fi,1 转移，只能使用 fi,2f_{i,2}fi,2 ，否则仍可以选择 fi,1f_{i,1}fi,1 进行转移。 注意 m=1m=1m=1 时只能选择第一层的那一个，之后的层由于封印规则无法继续选择。 我的代码中将 fi,1/2f_{i,1/2}fi,1/2 与 gi,1/2g_{i,1/2}gi,1/2 合并为一个结构体，从而方便排序。

明显的 DP。 设 dpi,jdp_{i,j}dpi,j 表示到达 iii 层，目前位于房间 jjj 的最大收获。 状态转移实在太显然了： dpi,j=max⁡(max⁡1≤k<jdpi−1,k,max⁡j<k≤mdpi−1,k)+ai,jdp_{i,j}=\max(\max_{1 \leq k < j}{dp_{i-1,k}},\max_{j < k \leq m}{dp_{i-1,k}})+a_{i,j} dpi,j =max(1≤k<jmax dpi−1,k ,j<k≤mmax dpi−1,k )+ai,j 发现可以边跑边记录上一层的最大值，这样转移复杂度就降为 O(1)O(1)O(1) 了。 但是如果上一层的最大值的位置刚好等于 jjj 的话，jjj 房间开不了门。所以我们还要维护一个次大值。 这就很简单了。 时间复杂度：O(nm)O(nm)O(nm) Code:

前缀和优化DP

动态规划 对于本题，我们先从常规思路入手，考虑从第 iii 层向第 i+1i + 1i+1 层的状态转移。设 f[i][j]f[i][j]f[i][j] 表示处于第 iii 层的第 jjj 个房间时所能取得的最大值。那么状态转移方程为 f[i+1][k]=max⁡(f[i][j])+a[i+1][k]f[i + 1][k] = \max(f[i][j]) + a[i + 1][k]f[i+1][k]=max(f[i][j])+a[i+1][k]，其中 j∈{1,2,⋯ ,n}j \in \{1, 2, \cdots, n\}j∈{1,2,⋯,n} 且 j≠kj \neq kj=k。 从这个转移方程可以看出，f[i+1][j]f[i + 1][j]f[i+1][j] 的转移核心在于找出第 iii 层除第 jjj 个房间之外能取得的最大价值。假设第 iii 层价值最大的房间编号为 jjj，那么在第 i+1i + 1i+1 层中，除了第 jjj 号房间外，其他房间都可以从第 iii 层的 jjj 号房间移动过来，从而获取最大价值。而第 i+1i + 1i+1 层的 jjj 号房间，则可以从第 iii 层价值次大的房间转移到达。 基于此，我们发现只需记录每一层价值最大的两个房间的编号，就能实现向下一层的状态转移。这种方法的时间复杂度为 O(nm)O(nm)O(nm)。 注意 m == 1的状况他会被困在第一层