跳石板题解 动态规划 递推

跳石板

https://www.nowcoder.com/practice/4284c8f466814870bae7799a07d49ec8

题目

有一系列石板，编号1,2,3,…，小明想要从 N 号到 M 号。给定整数 K，他每次可以往前跳 K 的因数步（除了 1 和 K）。问最少需要跳几次，不能到达输出 -1 。

(4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)

初印象

1. 每次跳相当于加一个数，基于加法交换律，跳的顺序是任意的。
2. 基于结合律，两个两步相当于一个四步。
3. 每次跳的步数大于 1

设 dp[i] 表示到第 i 号最少需要几步。（突然感觉有点像最长上升子序列）

可以枚举因数，尝试转移：dp[i] = min(dp[i-p]+1), p ∈K 的因数

笑***，题目理解错了，K 不是给定的：

对于小易当前所在的编号为K的石板，小易单次只能往前跳K的一个约数(不含1和K)步

不过好像问题不大，上面的是往前看，考虑到不能提前知道跳多少步，那就可以往前看，用递推的方式往后推。

至于找因数最简单的是枚举，复杂度是 O ( n ) {O}(\sqrt n ) O(n ​)

#include#include#includeusing namespace std;const int N = 200010;int ans[N];int main(void) {    int n, m;    cin >> n >> m;    for (int i = 0; i