跳石板__牛客网

小渣渣渣渣渣渣

#过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)

、小白念念so

动态规划
思路：定义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)

superyouyo

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

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)

rs勿忘初心

#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)

pein531

暴力递归：

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

记忆化搜索

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

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)

C++

喝醉了Ta的梦,晚安

#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)

C/C++

WZ_Dale

借鉴别人的解法：来源：牛客网

链接：https://www.nowcoder.com/questionTerminal/4284c8f466814870bae7799a07d49ec8?toCommentId=6282257&ran=320

动态规划:

采用动态规划思想求解。创建一个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)

C/C++

ゆなちゃん

当时程序就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)

C/C++

lewis_c++

考虑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)

C/C++

nbgao

#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)

one_time_ac

#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)

ayonel

广搜，注意求质数，以及求因数时的一些优化

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)

Leoric

用筛法求出每个数的所有约数，设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)

RampageNK

内存超限

#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)

O`Neal

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)

跳石板

输入描述:

输出描述:

输入

输出

暴力递归：

记忆化搜索

问题信息

热门推荐

通过挑战的用户

相关试题