首页 > 试题广场 >

跳石板

[编程题]跳石板
  • 热度指数:37114 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小易来到了一条石板路前,每块石板上从1挨着编号为:1、2、3.......
这条石板路要根据特殊的规则才能前进:对于小易当前所在的编号为K的 石板,小易单次只能往前跳K的一个约数(不含1和K)步,即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板,他想跳到编号恰好为M的石板去,小易想知道最少需要跳跃几次可以到达。
例如:
N = 4,M = 24:
4->6->8->12->18->24
于是小易最少需要跳跃5次,就可以从4号石板跳到24号石板

输入描述:
输入为一行,有两个整数N,M,以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)


输出描述:
输出小易最少需要跳跃的步数,如果不能到达输出-1
示例1

输入

4 24

输出

5
借鉴别人的解法:来源:牛客网
动态规划:
采用动态规划思想求解。创建一个vector容器steps,steps[i]表示到达i号石板所需的最小步数。初始化为steps容器为INT_MAX。从序号N的石板开始逐个遍历,若steps[i]为INT_MAX,表示该点不可到达,直接开始下次循环。若steps[i]不为INT_MAX,表示该点可以到达,下面求解编号i的约数,进行动态规划。动态规划的转移方程为
steps[i+j] = min(steps[i]+1,steps[i+j])   //i为石板编号,j为i的约束
steps[N] = 0
解法代码如下:
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
    int N,M;
    while(cin>>N>>M){
        vector<int> steps(M+1,INT_MAX);
        steps[N] = 0;
        for(int i=N;i<=M;i++){
            if(steps[i] == INT_MAX){
                continue;
            }
            for(int j=2;(j*j)<=i;j++){
                if(i%j == 0){
                    if(i+j <= M){
                        steps[i+j] = min(steps[i]+1,steps[i+j]);
                    }
                    if(i+(i/j) <= M){
                        steps[i+(i/j)] = min(steps[i]+1,steps[i+(i/j)]);
                    }

                }

            }
        }
        if(steps[M] == INT_MAX){
            steps[M] = -1;
        }
        cout<<steps[M]<<endl;
    }
    return 0;
}
编辑于 2020-06-09 09:32:32 回复(0)
更多回答
#过80%,尽力了
l=(input().split())
n,m=int(l[0]),int(l[1])
p=[-1]*(m-n+1)
p[0]=0
for i in range(m-n-1):
    if p[i]!=-1:
        kk=i+n
        for j in range(2,min(int((n+i)**(1/2))+1,(len(p)-i)//2)):
            if kk%j==0:
                a=kk//j+i
                aa=j+i
                if p[aa]==-1 or p[aa]>p[i]+1:
                    p[aa]=p[i]+1
                if a<len(p):
                    if p[a]==-1 or p[a]>p[i]+1:
                        p[a]=p[i]+1
print(p[-1])
发表于 2018-01-11 21:07:49 回复(0)
动态规划
思路:定义jump[]数组,jump[n]表示调到整数n所用的最小步数。
初始化,jump[n ~ m] 为-1。
状态转移方程,对第k步,我们找到所有满足jump[x] == k - 1的石板,然后更新jump数组,更新的方法是从jump[x]向后跳一步y,y是x的除1和x的约数,即
if (jump[x + y] != -1) jump[x + y] = jump[x] + 1
从步数为1开始迭代。
结束的条件,为jump[M] != -1,表示找到了到达整数M石板的最小步数; 
或者 对当前步数k找不到满足(N <= x <= M) jump[x] == k - 1的石板,等价于说我们要找的石板越界了,第k-1步能到达的石板肯定大于M,你仔细想一想。

/**
 * Created by arrow on 11/19/17.
 */
public class Question {
    public static int jumpTimes(int N, int M) {
        // jump数组表示调到jump[i]所用的最大步数
        int[] jump = new int[M + 1];

        // 初始化jump数组为-1
        for (int i = N; i <= M; ++i) {
            jump[i] = -1;
        }

        int step = 1;
        jump[N] = 0;

        // printState(jump, N);
        while (jump[M] == -1) {
            int max_step = Integer.MIN_VALUE;

            for (int cur = N; cur <= M; ++cur) {
                if (jump[cur] > max_step)
                    max_step = jump[cur];

                if (jump[cur] < step - 1)
                    continue;
                // 找到step-1步所能走到的石板
                else if (jump[cur] == step - 1) {

                    for (int k = 2; k <= Math.sqrt(cur); ++k) {
                        // System.out.println("cur = " + cur + ", k = " + k);
                        // 找到约数k,更新jump数组
                        if (cur % k == 0) {
                            if (cur + k <= M && jump[cur + k] == -1) jump[cur + k] = step;
                            if (cur + cur / k <= M && jump[cur + cur / k] == -1) jump[cur + cur / k] = step;
                        }
                    }
                } else {
                    continue;
                }
            }

            // 当前步数和jump数组中最大的步数相差2,
            // 等价于是找不到step-1步所能走到的石板了,因为越界了,所以循环结束
            if (step - max_step > 1)
                break;

            step++;
            // printState(jump, N);
        }

        // printState(jump, N);
        return jump[M];
    }

    // 打印状态数组
    private static void printState(int[] jump, int N) {
        System.out.println("JUMP");
        for (int i = N; i < jump.length; ++i) {
            System.out.printf("%5d ", i);
        }
        System.out.println();
        for (int i = N; i < jump.length; ++i) {
            System.out.printf("%5d ", jump[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int result = jumpTimes(N, M);
        System.out.println(result);
    }
}

发表于 2017-11-19 02:25:47 回复(0)

广度优先搜索,同时搜过的点不再搜,肯定步数比上一次搜索要大。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Queue<Integer> queue = new LinkedList<Integer>();
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        ArrayList<Integer> factor = new ArrayList<Integer>();
        queue.add(n);
        map.put(n, 0);
        int i,j;
        while(!queue.isEmpty()) {
            int head = queue.poll();
            factor = getAppNums(head);
            if(head == m) {
                System.out.print(map.get(head));
                return;
            }
            for(i=0;i<factor.size();i++) {
                if(!map.containsKey(head+factor.get(i)) && head+factor.get(i)<=m) {
                    queue.add(head+factor.get(i));
                    map.put(head+factor.get(i), map.get(head)+1);
                }
            }
        }
        System.out.print(-1);
    }

    public static ArrayList<Integer> getAppNums(int n) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                list.add(i);
                if (n / i != i) {
                    list.add(n / i);
                }
            }
        }
        return list;
    }
}
发表于 2017-08-13 17:06:23 回复(2)
#include <stdio.h>
#include <vector>
#include <iostream>
#include <memory.h>
#include "math.h"
using namespace std;

void findYueShu(int x,vector<int> &a){
    for(int i = 2;i<=(int)sqrt((double)x);++i){
        if(x%i == 0){
            a.push_back(i);
            if(x/i != i)
                a.push_back(x/i);
        }
    }
}

int main(){
    int n,m;
    while(cin>>n>>m){
        //动态规划
        int* buf = new int[m+1];
        memset(buf,0,sizeof(int)*(m+1));
        buf[n] = 1;
        for(int i = n;i<m;++i){
            //找到i所对应的约数容器
            if(buf[i] == 0)
                continue;
            vector<int> yueshu;
            findYueShu(i,yueshu);
            for(auto it = yueshu.begin();it!=yueshu.end();++it){
                if((i+*it)<=m){
                    if(buf[i+*it] != 0)
                        //发生冲突
                    	buf[i+*it] = min(buf[i+*it],buf[i]+1);
                    else
                        buf[i+*it] = buf[i]+1;
                }         
            }
        }
        if(buf[m] == 0)
            cout<<-1<<endl;
        else
            cout<<buf[m]-1<<endl;
        delete[] buf;
    }
}

发表于 2017-02-08 13:30:55 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define INT_MAX 100001
int main()
{
	int n, m;
	while(cin >> n >> m)
	  {
		 vector<int> dp(m + 1, INT_MAX);  //dp[i]为在第i个石板时,所需要的步数,初始设为条件范围内的最大值
		 dp[n] = 0;
		 for (int i = n; i <= m; i++)
			{
			 for (int j = 2; j*j <= i; j++)   //比如i为8,当找到i的一个约数j为2时,另一个约数就为i/j
			    {                             //所以只需要找j*j<=i,事实上如果不这样做,部分用例运行超时
				 if (i%j == 0)
					{
					  if (i + j <= m)
						 dp[i + j] = min(dp[i + j],dp[i]+1);
                      if(i+i/j<=m) //关键步骤
                         dp[i + i/j] = min(dp[i + i/j],dp[i]+1);
					}
			    }
           }
       if(dp[m]==INT_MAX)
           cout<<"-1"<<endl;
       else
           cout<<dp[m]<<endl;
	 }
}

发表于 2017-09-02 09:53:12 回复(0)

暴力递归:

枚举一般位置的情况,到达位置时,可以再往右走的约数步(除开1和本身),直到抵达终点时更新最小步数就好,如果当前位置超过了,表明本次的跳跃策略是无效的。

记忆化搜索

整个尝试的逻辑非常简单,但我们可能反复到达某个位置,而这个位置在第二次到达的时候,我们并没有必要重复计算从它到终点需要的最少步数(如果从它根本不可能到终点,那就更没有必要继续递归展开)。因此可以加个缓存表记录已经计算过的结果,从而避免重复递归展开计算。

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        int[] dp = new int[m + 1];
        Arrays.fill(dp, -1);
        int ans = dfs(n, m, dp);
        System.out.println(ans == Integer.MAX_VALUE? -1: ans);
    }

    private static int dfs(int cur, int end, int[] dp) {
        if(cur == end){
            return 0;         // cur=end时还需要0步到达终点
        }else{
            if(dp[cur] != -1 || dp[cur] == Integer.MAX_VALUE){
                return dp[cur];      // -1表示还没算过,得算;整数最大值表示到不了,直接返回;其他正数表示已经有结果了,直接返回。
            }
            int pNext = Integer.MAX_VALUE;
            // 当前位置是cur,尝试所有能走的步数
            for(int i = 2; i <= (int)Math.sqrt(cur); i++){
                if(cur % i == 0){
                    // 计算后续还有几步能到终点
                    if(cur + i <= end){
                        pNext = Math.min(pNext, dfs(cur + i, end, dp));
                    }
                    if(cur / i != i && cur + cur/i <= end){
                        pNext = Math.min(pNext, dfs(cur + cur/i, end, dp));
                    }
                }
            }
            if(pNext != Integer.MAX_VALUE){
                dp[cur] = 1 + pNext;      // 能到就加一步
            }else{
                dp[cur] = pNext;          // 返回最大值表示到不了
            }
            return dp[cur];
        }
    }
}

根据这个递归的做法,还可以进一步优化为动态规划版本。但如果笔试时赶时间,建议就直接提交记忆化搜索的版本,一般情况下复杂度与动态规划相同。

发表于 2022-04-11 15:20:55 回复(0)
#include<iostream>
using namespace std;
#include<vector>
#include<limits.h>
#include<math.h>

void getDiv(int x,vector<int>& a)
{
    for(int i=2;i<=sqrt(x);++i)
    {
        if(x%i == 0)
        {
            a.push_back(i);
            if(x/i != i)
                a.push_back(x/i);
        }
    }
}

int getMinStep(int n,int m)
{
    vector<int> step(m+1,INT_MAX);
    //初始化
    step[n] = 0;
    for(int i=n;i<m;++i)
    {
        if(step[i]==INT_MAX)
            continue;
        vector<int> a;
        getDiv(i,a);
        
        for(int j=0;j<a.size();++j)
        {
            if(i+a[j]<=m && step[i+a[j]]==INT_MAX)//第一次涉足这个台阶
            {
                step[i+a[j]] = step[i] + 1;
            }
            else if(i + a[j] <= m)//不是第一次涉足,比较取最小值,动态规划核心算法
            {
                step[i+a[j]] = step[i] + 1 < step[i+a[j]] ? 
                    step[i] + 1 : step[i+a[j]];
            }
        }
    }
    return step[m]==INT_MAX?-1:step[m];
}

int main()
{
    int N,M;
    cin>>N>>M;
    cout<<getMinStep(N,M)<<endl;;
    return 0;
}

发表于 2021-10-27 17:01:28 回复(0)
//广度优先遍历

import java.util.*; public class Main{     public static void main(String[] args){         Scanner input=new Scanner(System.in);         while(input.hasNext()){             int N=input.nextInt();             int M=input.nextInt();             HashMap<Integer, Integer> list=new HashMap<>();             LinkedList<Integer> queue=new LinkedList<>();             list.put(N, 0);   //当前所在位置,0步             queue.add(N);             while(!queue.isEmpty()){                 int num=queue.remove();                 if(num==M){        //满足条件时,输出                     System.out.println(list.get(num));                     return ;                 }                 if(num>M)     //石板超过目标时不考虑                     continue;                 HashSet<Integer> arr=new HashSet<>();   //存储当前石板的所有约数                 yueShu(num, arr);                //找约数                 for(int elem: arr){                     if(!list.containsKey(num+elem)){     //记录下一次起跳时的石板                         list.put(num+elem, list.get(num)+1);                         queue.add(num+elem);                     }                 }             }             System.out.println(-1);         }     }     public static void yueShu(int num, HashSet<Integer> arr){    //约数计算         for(int i=2; i<=Math.sqrt(num); i++){             if(num%i==0){                 arr.add(i);                 arr.add(num/i);             }         }     } }

编辑于 2018-05-28 19:13:50 回复(0)
当时程序就8 85678这组样例没过,于是追踪了一下这组的跳跃走势,结果如下
85678(32)

85676(31)

64257(30)

42838(29)

42836(28)

42834(27)

28556(26)

21417(25)

14278(24)

12980(23)

9735(22)

6490(21)

5192(20)

3894(19)

2596(18)

1947(17)

1298(16)

1296(15)

864(14)

576(13)

384(12)

256(11)

192(10)

128(9)

96(8)

64(7)

48(6)

32(5)

24(4)

16(3)

12(2)

10(1)***********************

8(0)

问题出现了,8是可以直接跳到12的,为啥多跳了个10,不解
然后发现8的因子只有2- -||
然后回查求因子的函数发现好像是多剪了个枝导致的
去掉后AC

可以在头文件后面#define debug追踪该点是从哪里跳过来的(下面参数tracking为要追踪的数(比如85678),N和M是题目的N和M),追完一个后可以把tracking改为上一次trackfrom的结果继续追踪

#include<stdio.h>
#include<math.h>

#ifdef debug
#define tracking 85678
#define N 8
#define M 85678
#endif

int yue(int x, int* res){
    int i=2;
    int nums=0;
    for(i=2;i<=sqrt((double)x);i++){
        if(x%i==0){
            res[nums++]=i;
            res[nums++]=x/i;
        }
    }
    return nums;
}
int main(){
    int i,j;
#ifndef debug
    int N,M;
#else
    int trackfrom;
#endif
    int steps[100001];
#ifndef debug
    scanf("%d%d",&N,&M);
#endif
    for(i=N;i<=M;i++)steps[i]=100001;
    steps[N]=0;
    for(i=N;i<=M-1;i++){
        if(steps[i]!=100001){
            int q,yues[500]={0};
            int cc = yue(i,yues);
            int mul=0;
#ifdef debug
            printf("i=%d,",i);
            for(q=0;q<cc;q++)printf(" %d",yues[q]);
            printf("\n");
#endif
            for(mul=0;mul<cc;mul++){
                if(i+yues[mul]<=100000)
                {
                    if(steps[i]+1<steps[i+yues[mul]]){
                        steps[i+yues[mul]]=steps[i]+1;
#ifdef debug
                        printf("step [%d] is set to %d, from [%d]\n",i+yues[mul],steps[i]+1,i);
                        if(i+yues[mul]==tracking)trackfrom=i;
#endif
                    }
                }
            }
        }
    }
#ifdef debug
    if(steps[tracking]!=100001)printf("tracking %d,result=%d,trackfrom %d\n",tracking,steps[tracking], trackfrom);
#else
    if(steps[M]!=100001)printf("%d\n",steps[M]);
#endif
    else printf("-1\n");
    return 0;
}

发表于 2018-05-04 11:55:05 回复(0)
考虑N,M的取值范围,dfs首先不考虑,因为有明显的记忆过程,所以考虑使用动态规划。
构造dp矩阵,dp[M+1],dp[M]表示,从N——>M的最少步骤,显然可以得到条件,dp[N]=0,
设其他值为INT_MAX。 对于dp[N] 遍历N的因子(sub[i-j]) dp[N+sub[i-j]]即为可到达
且从N一步到达,这里dp[N+sub[i-j]]和dp[N]+1取最小值即可。

//小易居然又开始跳石板了...他肯定是疯了
#include<bits/stdc++.h>
using namespace std;
//保存因子,这里不能暴力求因子,会超时,要i×i<=n,同时保存除数和被除数。
void getsub(vector<int>&,int);
int main()
{
    int N,M;
    cin>>N>>M;
    vector<int>sub;
    vector<int>dp(M+1,INT_MAX);
    dp[N]=0;
    //构造dp矩阵
    for(int i=N;i<=M;++i){
        if(dp[i]==INT_MAX)
            continue;
        getsub(sub,i);
        for(int j=0;j<sub.size();++j){
            if(i+sub[j]<=M)
                dp[i+sub[j]]=min(dp[i+sub[j]],dp[i]+1);
        }
    }
    if(dp[M]==INT_MAX)
        cout<<-1<<endl;
    else
        cout<<dp[M];
    return 0;
}
void getsub(vector<int>&sub,int num)
{
    sub.clear();
    for(int i=2;i*i<=num;++i){
        if(num%i==0){
            sub.push_back(i);
            if(i!=num/i)
                sub.push_back(num/i);
        }
    }
}

发表于 2018-04-19 15:03:05 回复(0)
#include <iostream>
#include <climits>
#include <vector>
using namespace std;

int main()
{     int N,M;     while(cin>>N>>M)     {         vector<int> steps(M+1, INT_MAX);         steps[N] = 0;         for(int i=N;i<=M;i++)         {             if(steps[i] != INT_MAX)                 for(int j=2;j*j<=i;j++)                 {                     if(i%j == 0)                     {                         if(i+j <= M)                             steps[i+j] = min(steps[i]+1, steps[i+j]);                         if(i+i/j <= M)                             steps[i+i/j] = min(steps[i]+1, steps[i+i/j]);                     }                 }         }         if(steps[M] == INT_MAX)             steps[M] = -1;         cout<<steps[M]<<endl;     }         return 0;
}


发表于 2018-01-28 00:23:48 回复(0)
import java.util.*;

/**
 * 题目描述
 * 小易来到了一条石板路前,每块石板上从1挨着编号为:1、2、3.......
 * 这条石板路要根据特殊的规则才能前进:对于小易当前所在的编号为K的 石板,
 * 小易单次只能往前跳K的一个约数(不含1和K)步,即跳到K+X(X为K的一个非1和本身的约数)的位置。 
 * 小易当前处在编号为N的石板,他想跳到编号恰好为M的石板去,小易想知道最少需要跳跃几次可以到达。
 * 
 * 例如:
 * N = 4,M = 24:
 * 4->6->8->12->18->24
 * 于是小易最少需要跳跃5次,就可以从4号石板跳到24号石板
 * 输入描述:
 * 输入为一行,有两个整数N,M,以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)

 * 输出描述:输出小易最少需要跳跃的步数,如果不能到达输出-1
 * 示例
 *      输入4 24
 *      输出5
 *
 * 
 * 掉的坑:
 * 1.使用(m == n) ( [-128, 127] 时相等 )
 */
public class 挑石板 {

    public static void main(String[] args) {

        //输入
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        Integer m = sc.nextInt();
        Integer result = -1;

        //处理
        if (m.equals(n)) {
            System.out.println(0);
        } else {
            int step[] = new int[m + 1];
            step[n] = 0;
            for (int i = n; i < m; i++) {
                Set<Integer> factor = getFactor(i);
                for (Integer j : factor) {
                    if (i % j == 0 && j <= m - i) {
                        if (step[j + i] > step[i] + 1 || step[i + j] == 0 && (step[i] != 0 || i == n)) {
                            step[j + i] = step[i] + 1;
                        }
                    }
                }
            }

            //输出
            if (step[m] == 0)
                System.out.println(-1);
            else
                System.out.println(step[m]);
        }

    }

    private static Set<Integer> getFactor(Integer n) {
        Set<Integer> res = new HashSet<>();
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                res.add(i);res.add(n/i);
            }
        }
        return res;
    }
}
发表于 2018-01-08 19:28:39 回复(0)
#include <iostream>
#include <vector>

using namespace std;
void GetFewNum(int num, vector<int> &a)
{
	int tem = sqrt(num);
	for (int i = 2; i <= tem; i++)
	{
		int temp = num / i;
		if (temp == num / i)
		{
			if (temp != i)
			{
				a.push_back(temp);
				a.push_back(i);
			}
			else
				a.push_back(i);
		}
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> res(m+1,0);
	int k = n;
	res[k] = 1;
	while (k<=m)
	{
		if (res[k] == 0)
		{
			k++;
			continue;
		}
		vector<int> a;
		GetFewNum(k,a);
		for (int i = 0; i < a.size(); i++)
		{
			if (a[i] + k <= m && res[a[i] + k] == 0)
			{
				res[a[i] + k] = res[k] + 1;
			}
			else if (a[i] + k <= m && res[a[i] + k] != 0)
			{
				res[a[i] + k] = res[a[i] + k] < res[k] + 1 ? res[a[i] + k] : res[k] + 1;
			}
		}
		k++;
	}
	if (res[m] != 0)
		cout << res[m] - 1 << endl;
	else
		cout << -1 << endl;
	return 0;
}

发表于 2017-11-01 16:28:43 回复(0)
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in 

);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(a==b){
			System.out.println(0);
		}else {
			int []c = new int [b+1];
			for(int i = a ; i < b ; i++ ){
				for(int j = 2 ; j <= Math.sqrt(i) ; j++ ){
					if(i/j*j==i){
						if((i==a||c[i]!=0)&&i+i/j<=b){
							if(c[i+i/j]==0||c[i+i/j]>c[i]+1){
								c[i+i/j]=c[i]+1;
							}
						}
						if((i==a||c[i]!=0)&&i+j<=b){
							if(c[i+j]==0||c[i+j]>c[i]+1){
									c[i+j]=c[i]+1;
							}
						}
					}
				}
			}
			System.out.print(c[b]==0?-1:c[b]);
		}

	}

}
想了好久,开始一直都没想到(i==a||c[i]!=0)

编辑于 2017-09-06 08:52:05 回复(0)
#include<stdio.h>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
int book[200005];
struct node{
	int val,step;
	node(int val,int step):val(val),step(step){}
};
int main(){
	int N,M,i;
	//freopen("input.txt","r",stdin);
	while(scanf("%d%d",&N,&M)!=EOF){
		memset(book,0,sizeof(book));
		queue<node> Q;
		Q.push(node(N,0));
        book[N]=1;
		int flag=-1;
		while(!Q.empty()){
			node head=Q.front();Q.pop();
			if(head.val==M){
				flag=head.step;
				break;
			}
			if(head.val>M) continue;
			int n=(int)sqrt(head.val);
			for(i=2;i<=n;i++)
				if(head.val%i==0){
					int other=head.val/i;
                    if(book[head.val+i]==0){
						Q.push(node(head.val+i,head.step+1));
                        book[head.val+i]=1;
                    }
					if(other!=i&&book[head.val+other]==0){
						Q.push(node(head.val+other,head.step+1));
                        book[head.val+other]=1;
                    }
				}
		}
		printf("%d\n",flag);
	}
}//直接bfs就可以啦~

发表于 2017-08-30 11:41:26 回复(2)
广搜,注意求质数,以及求因数时的一些优化
package 跳石板;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

/**
 * @author ayonel
 * @create 2017-08-28 22:09
 * @blog https://ayonel.me  * 广搜
 **/
public class Main {
    public static boolean[] notPrime;
    public static boolean[] visited;
    public static void genPrime(int n){
        notPrime = new boolean[n+1];
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                for (int j = 2; i*j < n; j++) {
                    notPrime[i*j] = true;
                }
            }
        }

    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        if (M==N){
            System.out.println("0");
            return;
        }
        visited = new boolean[M+1];
        visited[0] = true;
        visited[1] = true;
        genPrime(M);
        Deque<Integer> deque = new ArrayDeque<>();
        Deque<Integer> deep = new ArrayDeque<>();
        deque.push(N);
        deep.push(0);
        int node,dep, fac1, fac2;

        while (!deque.isEmpty()){
            node = deque.poll();
            dep = deep.poll();

            if (!notPrime[node]){
                //质数
                continue;
            }
            for (int j = 2; j <= (int)Math.sqrt(node); j++) {

                if (node % j == 0){
                    fac1 =  node+j;
                    fac2 = node+node/j;
                    if (fac1 == M||fac2 == M){
                        System.out.println(dep+1);
                        return;
                    }

                    if (fac1<=M && notPrime[node+j] && !visited[node+j]){
                        deque.offer(fac1);
                        deep.offer(dep+1);
                        visited[fac1] = true;
                    }
                    if (fac1 != fac2 && fac2 <= M && notPrime[fac2] && !visited[fac2]){
                        deque.offer(fac2);
                        deep.offer(dep+1);
                        visited[fac2] = true;
                    }
                }
            }
        }
        System.out.println(-1);

    }


}


发表于 2017-08-28 23:46:01 回复(0)
用筛法求出每个数的所有约数,设dp[ k ] 为到达k的最小步数,对于k的约数kk有状态转移方程
dp[ k+kk ]=min( dp[ k+kk ] , dp[ k ]+1)。

总时间复杂度为筛法的时间复杂度O( nlogn)。


#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<queue>
#include<fstream>
#include<stdlib.h>
#include<ctime>
#include<vector>
using namespace std;
#define FOR(i,LE,RI) for(i=LE;i<RI;++i)
#define MEM(x,i) memset(x,i,sizeof(x))
#define COUT(DATA,ED) printf("%d%c",DATA,ED)
#define CIN(val)  scanf("%d",&val)
#define LL long long
const int LE=2000000;
const int INF=2000000;
int dp[120000];
int dest[LE],nxt[LE];
int first[210000],zz;
int n;
void one_set(int val){
	for(int alt=first[val];alt!=-1;alt=nxt[alt]){
		int sum=dest[alt]+val;
		if(sum>n) continue;
		dp[sum]=min(dp[sum],dp[val]+1);
	}
}
void init(){
	int i,j;
	int start,result;
	CIN(start);
	CIN(n);
	MEM(first,-1);
	zz=0;
	FOR(i,2,n+1){
		dp[i]=INF;
		FOR(j,2,n+1){
			if(i*j>n) break;
			dest[zz]=i;
			nxt[zz]=first[i*j];
			first[i*j]=zz++;
		}
	}
	dp[start]=0;
	FOR(i,start,n+1){
		one_set(i);
	}
	if(dp[n]>n) dp[n]=-1;
	COUT(dp[n],'\n');
	
	
}
int main(){
	init();
    return 0;
}

发表于 2017-08-24 16:30:41 回复(0)
内存超限
#include <iostream>
#include <vector>
using namespace std;
 
inline void divisor(const int& n,vector<int>& vec)
{
     
    for(int i=2;i<n;i++)
    {
        if(n%i == 0) vec.push_back(i);
    }
         
}
 
inline void ConstructTree(const vector<int>& vec,int depth,int& m)
{
    if(m>100000) return;
    vector<int> next_depth;
    for(int i=0;i<vec.size();i++)
    {
        vector<int> divisors;
        divisor(vec[i],divisors);
        for(int j =0;j<divisors.size();j++)
        {
            divisors[j]+=vec[i];
            if(divisors[j]==m) {cout<<depth+1<<endl;return;}
            if(divisors[j]<m)  next_depth.push_back(divisors[j]);
        }
    }
    ConstructTree(next_depth,depth+1,m);
     
}
 
int main()
{
    int n,m;
    cin>>n>>m;
    int depth=0;
    vector<int> init_vec;
    init_vec.push_back(n);
    ConstructTree(init_vec,depth,m);
    //cout<<setp<<endl;
    return 0;
}


编辑于 2017-08-12 13:55:32 回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{
public static void main(String[] args) { // TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
System.out.println(jumpStone_dp(N,M)); }
private static int jumpStone_dp(int n, int m) { //动态规划求步数,O((m-2)*m^1/2)=O(n^(3/2))
// TODO Auto-generated method stub
int dp[] =new int[m+1];
for(int i=2;i<m+1;i++)
dp[i] = (i==n)? 0:Integer.MAX_VALUE;        //使用MAX_VALUE表示不可达
for(int j=n;j<=m-2;j++){ //这里j自增到m-2而不是m
if(dp[j]==Integer.MAX_VALUE) continue;
List divisors = getDivisor_dp(j);
if(null == divisors) continue;
for(int i=0;i<divisors.size();i++){
if(divisors.get(i)+j>m) continue;
/*关键代码,dp[i]表示当值为i时,从n增加到i的最小步数,首先遍历从n到m的所有数,并在每次遍历中找到当前数i的所有约数,这样就知道了i的下一步可以到达哪些数字,然后Math取最小值*/
dp[divisors.get(i)+j] = Math.min(dp[divisors.get(i)+j], dp[j]+1);
}
}
if(dp[m]==Integer.MAX_VALUE) return -1;
return dp[m];
}
private static List getDivisor_dp(int n) { //求约数集合,算法复杂度n^1/2
// TODO Auto-generated method stub
if(n<3) return null;
List list = new ArrayList();
for(int i=2;i<=Math.sqrt(n);i++){
if(n%i == 0) {
list.add(i);
if(n/i!=i) list.add(n/i);
}
}
return list;
}
}
编辑于 2017-07-30 19:43:43 回复(0)