跳石板

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

题目

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

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

初印象

每次跳相当于加一个数，基于加法交换律，跳的顺序是任意的。基于结合律，两个两步相当于一个四步。每次跳的步数大于 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

#include

using namespace std;

const int N = 200010;

int ans[N];

int main(void) {

int n, m;

cin >> n >> m;

for (int i = 0; i < N; i ++ ) {

ans[i] = 0x3f3f3f3f;

}

ans[n] = 0;

for (int i = n; i < m; i ++ ) {

set elem;

for (int j = 2; j * j <= i; j ++ ) {

if (i % j == 0) {

elem.insert(j);

elem.insert(i / j);

}

}

for (int j: elem) ans[i+j] = min(ans[i + j], ans[i] + 1);

}

cout << "m is " << m << endl;

if (ans[m] == 0x3f3f3f3f) cout << -1 << endl;

else cout << ans[m] << endl;

return 0;

}

奇怪的 bug：

不能用memset数组要开得够大，十万不够

参考链接

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。