首页 > 试题广场 > 跳石板
[编程题]跳石板
  • 热度指数:28824 时间限制: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
/*思路 从m 到n 至少需要多少步
* mark[i]记录到达位置i的最少步数。初始化mark[],起始位置mark[m]为0外,其它位置都为无穷大
* i~[m,n-2]依次更新mark[]:
* 判断,如果mark[i]为无穷大,则说明该位置不可由m到达,那么该位置也就到不了n。跳过,不作处理。减枝。
* 如果mark[i]不是无穷大,计算i的因子,对每一个因子求出i的下一步的位置tmp,如果mark[tmp]>mark[i]+1,更新mark[tmp]=mark[i]+1;
* 最终结果是mark[n],如果mark[n]是无穷大,则输出-1;否则返回mark[n]。
*/ 
/*
* 比如以8开始 mark[8]=0,8的因子list={2,4},
* factor=2,可到达10,mark[10]原本是无穷大,现在更新mark[10]=mark[8]+1;12同理。
* 循环下一个i=9,mark[9]是无穷大,跳过,不用处理。
* 也就是由8产生10和12,接下来就处理10,12及其产生的位置,而无需处理其他。
*/
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
    public static int deal(int m,int n){//m到n
    	int mark[]=new int[n+1];//记录到达每一个位置的步数
    	for(int i=m+1;i<=n;i++){                          //初始化 
    		mark[i]=Integer.MAX_VALUE;
    	}
    	for(int i=m;i<n-1;i++){                         //填mark[]
    		    if(mark[i]==Integer.MAX_VALUE)continue; //如果当前起始位置本身不可达 不作处理
    			ArrayList<Integer> list=allFactor(i);   //获得当前位置i的所有因子
    			for(int j=0;j<list.size();j++){         //计算i能到达的每一个位置tmp
    				int tmp=i+list.get(j);
    				int count=mark[i]+1;
    				if(tmp<=n&&mark[tmp]>count){        //如果从i到达位置tmp的次数比以前记录的小 更新mark[tmp]
    					mark[tmp]=count;
    				}
    			}	   		
    	}
    	return mark[n];
    }
	public static ArrayList<Integer>  allFactor(int n){//获得n的所有因子 除1 n外
		ArrayList list=new ArrayList();
		for(int i=2;i<=Math.sqrt(n);i++){
			if(n%i==0){
				list.add(i);
				if(i!=n/i)list.add(n/i);
			}
		}
		return list;
	}
    public static void main(String args[]){
    	Scanner sc=new Scanner(System.in);
    	 int m=sc.nextInt();
         int n=sc.nextInt();
         int r=deal(m,n);
         if(r==Integer.MAX_VALUE)r=-1;
         System.out.println(r);
        }   
}

编辑于 2017-08-16 09:11:07 回复(10)
  • 思路1:动态规划

采用动态规划思想求解。创建一个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;
}
  • 思路2:贪婪算法

贪婪算法并不一定能得到最优解,但是一个可行的,较好的解。

该问题若采用贪婪算法求解,并不会得到最优解,只会得到一个可行的,较好的解。例如,下述程序中采用了贪婪算法求解。每次都选取最大的约数前进一步。若后续发生不可到达目标点,则进行回溯,取第2大的约数作为步进值。下述程序通过率为80%,并不能AC。例如,对于N=676, M=12948情况,贪婪算法求解为13步,而动态规划算法求解为10步。

贪婪算法并不一定能得到最优解,但是一个可行的,较好的解。例如,给定硬币coins=[1,2,10,25],金额总数amounts=30,不限制每种币值的硬币数量,要求用所给硬币凑出所需金额,并且硬币数量最少。若采用贪婪算法求解,需要6枚(25+5*1)硬币。 若采用动态规划求解,所需3枚(10+10+10)硬币。 --- 贪婪算法

// 程序通过率为80%,并不能AC
//对于N=676, M=12948情况,贪婪算法求解为13步,而动态规划算法求解为10步。
// 贪婪算法并不一定能得到最优解,但是一个可行的,较好的解。
#include <iostream>
using namespace std;

int stepSearch(int N, int M) {
    if (N > M) {
        return -1;
    }
    if (N == M) {
        return 0;
    }
    int res = 0;
    for (int i = 2; i<N; i++) {
        if (i*(N / i) == N) {
            res++;
            if (stepSearch(N + N/i, M) != -1) {
                res += stepSearch(N + N/i, M);
                return res;
            }
            else {
                res--;
            }
        }
    }
    return -1;
}

int main() {
    int N, M;
    while (cin >> N >> M) {
        cout << stepSearch(N, M) << endl;
    }
    return 0;
}
发表于 2017-03-31 16:54:59 回复(7)
package com.suda.alex;

import java.util.ArrayList;
import java.util.Scanner;

public class Test3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			System.out.println(leastJumpTime(n, m));
		}
	}

	// 思想:动态规划
	public static int leastJumpTime(int n, int m) {
		if (m == n) {
			return 0;
		}
		int steps = m - n + 1;// 算上了起点和终点
		int[] dp = new int[steps];// 规划的量:到达 每个位置需要的最小步数
		dp[0] = 0; // 起点
		for (int i = 1; i < steps; i++) {
			dp[i] = Integer.MAX_VALUE; // 初始化 表示后续位置都不能到达
		}
		for (int i = 0; i < steps; i++) {
			// 0对应n石板 ;steps - 1 = m-n对应m石板
			if (dp[i] == Integer.MAX_VALUE) { // 该位置不能像前走
				dp[i] = 0;
				continue;
			}
			ArrayList<Integer> list = getAppNums(i + n); // i+n才是石板号
			for (int j = 0; j < list.size(); j++) {
				int x = list.get(j);
				if (i + n + x <= m) {
					dp[i + x] = Math.min(dp[i + x], dp[i] + 1);
				}
			}
		}
		if (dp[steps - 1] == 0) {
			return -1;
		} else {
			return dp[steps - 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;
	}
}


发表于 2016-09-26 20:53:29 回复(5)
我的想法是这样的, 先对N->M所有数,求其倍数,来计算每个数的约数
然后从N开始,加上其约数。广度遍历,直到到达M,或者不可达。
import sys
import collections

def jump(N, M):
    divs = [[] for _ in range(M+1)]
    for i in range(2, M+1):
        for j in range(i+i, M+1, i):
            divs[j].append(i)
    nums = 0
    stack = collections.deque()
    stack.append(N)
    cnt = 1
    while stack:
        print(stack)
        lenth = len(stack)
        for _ in range(lenth):
            n = stack.popleft()
            for i in divs[n]:  
##                if not (n % i):
                newn = n + i
                if newn == M:
                    return cnt
                elif not (1<<newn & nums) and newn < M:
                    nums ^= (1<<newn)
                    stack.append(newn)
        cnt += 1
    return -1

if __name__ == '__main__':
    try:
        std_in = sys.stdin
##        std_in = open("parlindromes.txt")
        while True:
            line = std_in.readline()
            if line == '':
                break
            line = [int(t) for t in line.splitlines()[0].split()]
            print(jump(line[0], line[1]))
    except:
        print(e)
        pass
TLE
应该是队列开销大? 
转变成DP 思路就是从N->M res[n] = min(res[n+dn], res[n]+1)
import sys
import collections

def jump(N, M):
    divs = [[] for _ in range(M+1)]
    for i in range(2, M+1):
        for j in range(i+i, M+1, i):
            divs[j].append(i)
    res = [0]*(M+1)
    res[N] = 1
    for n in range(N, M):
        if res[n]:
            for dn in divs[n]:
                if n + dn <= M:
                    res[n+dn] = min(res[n+dn], res[n] + 1) if res[n+dn] else res[n] + 1
    return res[M]-1 if res[M] else -1

if __name__ == '__main__':
    try:
        std_in = sys.stdin
##        std_in = open("parlindromes.txt")
        while True:
            line = std_in.readline()
            if line == '':
                break
            line = [int(t) for t in line.splitlines()[0].split()]
            print(jump(line[0], line[1]))
    except:
        pass


发表于 2017-03-24 09:46:53 回复(3)
#include<iostream>
#include<vector>
#include<set>
#include<math.h>
using namespace std;

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

int main(){
    int n,m;
    while(cin>>n>>m){
        vector<int> res(m+1, 0);
        res[n] = 1;
        for(int i=n;i<=m;i++){
            vector<int>a;
            //位置i无法到达,跳过
            if(res[i]==0)
                continue;
            get_yue_shu(i, a);
            //记录从起点到i的最小步数
            for(int j=0;j<a.size();j++){
                //由点i出发能到达的点
                if((a[j]+i)<=m&&res[a[j]+i]!=0)
                    //其它点也能到达,比较大小,记录最小步数
                    res[a[j]+i] = min(res[a[j]+i], res[i] + 1);
                else if((a[j]+i)<=m)
                    //到达点i的最小步数加1
                    res[a[j]+i] = res[i] + 1;
            }
        }
        if(res[m]==0)
            cout<<-1<<endl;
        else
            cout<<res[m]-1<<endl;
    }
    return 0;
}

发表于 2016-09-13 11:48:33 回复(2)

BFS + Visited Solution:
使用 Python 容易超时,下面这份代码为了不超时, 修改过很多次
如果是 C++ 的话应该按照思路写不会超时
这样看,写 python 的话还是 DP 好一些

N, M = list(map(int,input().strip().split()))
import math
def getAppNums(num):
    AppNums = []
    for i in range(2,int(math.sqrt(num))+1):
        if num % i ==0:
            AppNums.append(i)
            if num // i != i:
                AppNums.append(num//i)
    return AppNums
def solve():
    visited = set()
    level = [N]
    path = 0
    while level:
        temp = set()
        for l in level:
            divisors = getAppNums(l)
            for divisor in divisors:
                if l % divisor == 0:
                    position = l + divisor
                    if position == M:
                        return path+1
                    elif position not in visited and position< M:
                        temp.add(position)
                        visited.add(position)
        level = temp
        path += 1
    return -1
if N == M:
    print(0)
else:
    print (solve())
编辑于 2019-08-02 20:45:54 回复(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)
借鉴别人的解法:来源:牛客网
动态规划:
采用动态规划思想求解。创建一个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)
//广度优先遍历

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)