题解：P11827 [TOIP2024] 大步小步向前走

· · 题解

前言：此题解为搬运官方题解，非原创

（原链接：https://toip2024.twpca.org/editorial/editorial.html）

正文：

仅考虑最大步使用次数

当我们仅需要考虑最大步法使用次数最多时，可以定出以下状态：dp[i] = v，其中：

对于转移，我们能简单地枚举可用步法，去看可以从哪座非坑洞坐标跳到 i，总时间复杂度为 O((e - n) \times k) \le 3 \times 10^5。

考虑所有的步法使用次数

这里的做法意外的简单，我们使用同样的状态转移：dp[i] = v，但对于 v，我们将其定义为一个长度为 k 的阵列，其中 v[i] 的值代表着第 i 种步伐的使用次数。

如此一来，贸然进行相同的转移手段确实能得出解答，但想象上的时间复杂度为 O((e - n) \times k^2)，这里存在两种优化方式：

只储存有使用到的步法种类

注意到落脚在 i 时，至多只有 O(\sqrt i) 种使用到的步法种类，利用 std::vector 等数据结构储存并进行字典序比较，就可以用 O((e - n) \times k \times \sqrt e) 的时间复杂度通过本题。

只针对合法转移进行计算

实际上，只要在转移时忽略那些会转移到坑洞处的步法，总时间复杂度就会是 O((e - n) \times min(e - n,k) \times k)。由于 min(e - n,k) \le \sqrt {3 \times 10^5}，所以能够通过本题。

该时间复杂度是怎么得出的呢？ 上述算法的花费时间为转移次数乘上 k ，也就是说我们宣称总共的转移次数只有

该方法也是修改起来最为简单又容易忽略其时间复杂度正确性的做法。 ## 解答的回溯 以上提到的算法都需要在最后回溯出 dp 最佳解的转移过程，一个简单的方法便是直接对每个状态再纪录一个当前最佳解的转移来源，就可以从最终解答一路查表回到初始状态。 ## 一些题外话 实际上，可以利用一些哈希技巧搭配线段树等资料结构来维护每个 $dp[i]$ 的步法使用次数，并让两种步法次数的大小关系在数据结构上二分搜“最长共同前缀”来用 $O(\log k)$ 的时间复杂度完成比较，总时间复杂度可以进一步优化到 $O((e - n) \times k \log k)$。但由于该算法常数较大，在一般范围下不太能与前述的算法分出胜负。