题解 | #跳石板#

#include <cstdio>
#include <iostream>
#include<cmath>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int step[N];
int main() {
   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   int cur,to;
   scanf("%d%d",&cur,&to);
   step[cur] = 1;
   for(int i = cur; i < to; i++){
        if(!step[i])continue;
        for(int j = 2; j <= sqrt(i); j++){
            if(i % j == 0){
                if(i + j <= to &&!step[i + j]){
                    f[i + j] = f[i] + 1;
                    step[i + j] = 1;
                }else if(i + j <= to){
                    f[i + j] = min(f[i + j],f[i] + 1);
                }
                int k = i/j;
                if(i + k <= to && !step[i + k]){
                    f[i + k] = f[i] + 1;
                    step[i + k] = 1;
                }else if(i + k <= to){
                    f[i + k] = min(f[i + k],f[i] + 1);
                }
            }
        }
   }
//    for(int i = cur; i <= to; i++) printf("%d:%d %d\n",i,f[i],step[i]);
   if(!step[to]) puts("-1");
   else printf("%d\n",f[to]);


   return 0;
}
// 64 位输出请用 printf("%lld")

从开始石板cur一直到最后的石板进行遍历，对于每个位置标记可以未来到达的位置，如果对于当前位置可以到达，那么我们就以当前的石板为基准对于未来可能到达的石板的位置的步数进行求解，这样最后就可以求出是否到达to石板以及如果到达的最小步数是多少。

时间复杂度基本再n*根号n左右，由于有step数组标记实际上会快一些，但是数量级没有变化