代码理解不了,初学者不太懂

在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。
1<=L<=10^9,
1<=S<=T<=10,
1<=M<=100

输入描述:
第一行有一个正整数L ,表示独木桥的长度。
第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。
所有相邻的整数之间用一个空格隔开。

输出描述:
只包括一个整数,表示青蛙过河最少需要踩到的石子数。
示例1
输入
10
2 3 5
2 3 5 6 7
输出
2

https://www.nowcoder.com/questionTerminal/35ddfeb4e34f410bb9035682463a382f?answerType=1&f=discussion

 
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;
 
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
 
    // 注意 hasNext 和 hasNextLine 的区别
    while (in.hasNext()) { // 注意 while 处理多个 case
        int n = in.nextInt();
        int s = in.nextInt();
        int t = in.nextInt();
        int m = in.nextInt();
        ArrayList<Integer> stones = new ArrayList();
        for(int i=0;i<m;i++) {
            stones.add(in.nextInt());
        }
        Collections.sort(stones);
 
        if(s==t) {
            singleJudge(s,stones);
        } else {
            rangeJudge(s,t,n,stones);
        }
    }
}
 
public static void singleJudge(int s,ArrayList<Integer> stones) {
    int stoneNumber = 0;
    for(int i=0;i<stones.size();i++) {
        if(stones.get(i)%s == 0) {
            stoneNumber++;
        }
    }
    System.out.println(stoneNumber);
}
 
public static void rangeJudge(int s,int t,int n,ArrayList<Integer> stones) {
    int compressLen = compressBridgeLength(stones,n,t);
    int[] dp = new int[compressLen+t+1];
    Arrays.fill(dp,10000);
    dp[0] = 0;
    int stoneNumber = 10000;
    int maxStep = 0;
    for(int i=s;i<=compressLen+t;i++) {
        maxStep = Math.max(maxStep,i);
        for(int j=s;j<=t;j++) {
            if(i>=j) {
                dp[i] = Math.min(dp[i],dp[i-j]);
            }
        }
        if(stones.contains(i)) {
            dp[i] +=1;
        }
    }
 
    for(int i=compressLen;i<=maxStep;i++) {
        stoneNumber = Math.min(dp[i],stoneNumber);
    }
    System.out.println(stoneNumber);
}
 
public static int compressBridgeLength(ArrayList<Integer> stones,int n,int t) {
    for(int i=1;i<stones.size();i++) {
        int distance = stones.get(i) - stones.get(i-1);
        stones.set(i,stones.get(i-1) + distance%90);
    }
    n = (n - stones.get(stones.size()-1))%90 + stones.get(stones.size()-1);
    return n;
}
}
 

给你加了些注释

题解
先不考虑开不下数组的问题

如果我们用f[i]表示走到i这个位置的最小的踩石子的次数话

i这个位置没有石头:f[i]=min(f[i],f[k])

i这个位置是石头:f[i]=min(f[i],f[k]+1)

(k是上一步的位置, [公式] )

现在我们来解决桥太长了数组开不了的问题,我首先仔细看数据范围,相对于桥长度L,石头个数和青蛙跳跃范围S,T都是很小的,也就是说总是存在一些石头离得非常远,从前一个石头到这个石头需要跳很多步才能到达,而只要S和T不等,那么在这漫长的跳跃中我们总可以调整步幅使得踩不到这颗石子。换句话说,只要S和T不等当两个石子之间的距离超过了一定范围之后,任意距离都是可以到达的,这个时候两个离得很远的石头之间的距离就不重要了,那么现在我们就来考虑这个距离是多少:

(其实如果是比赛的时候,你其实可以根据时空限制直接估算这个值,能卡着时空过就行了)

我们先看例子,当S=3,T=4的时候那些长度是可以到达的:

3 、4、 6=3+3、 7=3+4、 8=4+4、 9=3+3+3、 10=3+3+4、 11=3+4+4、 12=4+4+4/3+3+3+3、13、14、15……

S=5,T=6时:

5、6、10=5+5、11=5+6、12=6+6、15=5+5+5、16=5+5+6、17=5+6+6、18=6+6+6、20=5+5+5+5、21=5+5+5+6、22=5+5+6+6、23=5+6+6+6、24=6+6+6+6、25=5+5+5+5+5、26=5+5+5+5+6、27=5+5+5+6+6、28=5+5+6+6+6、29=5+6+6+6+6、30=6+6+6+6+6/5+5+5+5+5+5……

我们发现,当长度超过 [公式] 之后,这个长度会有至少两种跳的方式(T个S相加和S个T相加),之后我们可以在每一步比都在较小的那种方法(T个S相加)的基础上将某些步的长度变大,然后就可以跳出更长的长度,也就是说 [公式] 及其之前的所有长度都可以跳出来,然后 [公式] 自然也有它自己的表达方式,之后的长度也都可以在S的整数倍的基础上调整得来。

对于本题来说,最大的 [公式] 的取值是 [公式] ,也就是说我们让任意两个距离大于90的石头距离为90就可以了,这样时间空间都满足了!

(S==T的情况直接特判)


 
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;
 
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
 
    // 注意 hasNext 和 hasNextLine 的区别
    while (in.hasNext()) { // 注意 while 处理多个 case
        int n = in.nextInt();//表示独木桥的长度。
        int s = in.nextInt();//表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数
        int t = in.nextInt();//表示青蛙一次跳跃的最大距离
        int m = in.nextInt();//桥上石子的个数
        ArrayList<Integer> stones = new ArrayList();
        for(int i=0;i<m;i++) {//第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。
//所有相邻的整数之间用一个空格隔开。
            stones.add(in.nextInt());
        }
        Collections.sort(stones);//对M个石子进行排序,从小到大
 
        if(s==t) {
            singleJudge(s,stones);//输出青蛙过河最少需要踩到的石子数
        } else {
            rangeJudge(s,t,n,stones);//s!=t时候执行
        }
    }
}
 
public static void singleJudge(int s,ArrayList<Integer> stones) {
    int stoneNumber = 0;
    for(int i=0;i<stones.size();i++) {
        if(stones.get(i)%s == 0) {
            stoneNumber++;
        }
    }
    System.out.println(stoneNumber);//表示青蛙过河最少需要踩到的石子数
}
 
public static void rangeJudge(int s,int t,int n,ArrayList<Integer> stones) {
    int compressLen = compressBridgeLength(stones,n,t);
    int[] dp = new int[compressLen+t+1];//定义数组长度为compressLen+t+1
    Arrays.fill(dp,10000);//给数组填充10000数据
    dp[0] = 0;//数组第一元素初始化0
    int stoneNumber = 10000;//石头数量
    int maxStep = 0;//最大步数
    for(int i=s;i<=compressLen+t;i++) {
        maxStep = Math.max(maxStep,i);//求最大步数
        for(int j=s;j<=t;j++) {//递归找到最小的
            if(i>=j) {
                dp[i] = Math.min(dp[i],dp[i-j]);//求dp[i],dp[i-j]中小的
            }
        }
        if(stones.contains(i)) {//石头中包含i
            dp[i] +=1;//加1
        }
    }
 
    for(int i=compressLen;i<=maxStep;i++) {//递归范围从maxStep,找到最小的石头
        stoneNumber = Math.min(dp[i],stoneNumber);//求dp[i],stoneNumbe中小的
    }
    System.out.println(stoneNumber);
}
 
public static int compressBridgeLength(ArrayList<Integer> stones,int n,int t) {
    for(int i=1;i<stones.size();i++) {
        int distance = stones.get(i) - stones.get(i-1);//求石头i和i-1距离
        stones.set(i,stones.get(i-1) + distance%90);//求石头i赋值第i-1个石头距离加上 石头i和i-1距离除以90余数
    }
    n = (n - stones.get(stones.size()-1))%90 + stones.get(stones.size()-1);
    return n;
}
}
 
 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.TreeSet;

//青蛙
public class Main {

// 用于储存某点的最少石头数,每次搜索时访问,若无记录添加并继续,若有记录比较,较多或相等则退出,较少则更新并继续
// key=long 位置
// value=int 最少踩到的石头数
    static HashMap<Long, Integer> stoneL = new HashMap<Long, Integer>();

// 用于储存石头的位置 用 containsKey(key)搜索
    static HashMap<Long, Integer> stoneP = new HashMap<Long, Integer>();

// 桥长long L
    static long l;

// 跳跃距离介于int S T
    static int s, t;

// 石子个数int M
    static int m;

// 用于实现广度搜索的栈 long 位置 int 石头数
    static TreeMap<Long, Integer> tm = new TreeMap<Long, Integer>();

    static TreeSet<Long> ts = new TreeSet<Long>();

// 递归广度搜索函数
    static void jump(long formPoint, int formStone) {

        for (int i = s; i < t + 1 && formPoint < l; i++) {
            long curPoint = formPoint + i;
            int curStone = formStone;
// 如果该点有石头,当前踩到石头数+1
            if (stoneP.containsKey(curPoint)) {
                curStone += 1;
            }
// 如果表中无该点数据,添加
            if (!stoneL.containsKey(curPoint)) {
                stoneL.put(curPoint, curStone);
                tm.put(curPoint, curStone);
// 如果有数据,进行比较
// 如果少于一直以来最少石头,更新
            } else if (curStone < stoneL.get(curPoint)) {
                stoneL.put(curPoint, curStone);
                tm.put(curPoint, curStone);
// 如果多于或等于已知最少石头,跳过
            } else {
                continue;
            }
        }

        while (!tm.isEmpty()) {
            long pointStack = tm.firstKey();
            int stoneStack = tm.get(pointStack);
            tm.remove(pointStack);

            jump(pointStack, stoneStack);
        }
    }

    public static void main(String[] args) throws Exception {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        l = Long.valueOf(br.readLine());
        l = 0;
        String str = br.readLine();
        String[] sstr = str.split(" ");
        s = Integer.valueOf(sstr[0]);
        t = Integer.valueOf(sstr[1]);
        m = Integer.valueOf(sstr[2]);
        str = br.readLine();
        sstr = str.split(" ");

        for (String ss : sstr) {
            ts.add(Long.valueOf(ss));
        }

        if (s == t) {
            int count = 0;
            for (Long sto : ts) {
                if (sto % s == 0) {
                    count++;
                }
            }
            System.out.println(count);
            return;
        }

        long yusto = 0;
        for (Long sto : ts) {
            if (sto - yusto > 81) {
                l += 81;
            } else {
                l = l + sto - yusto;
            }
            stoneP.put(l, 1);
            yusto = sto;
        }

        jump(0, 0);

        TreeMap<Long, Integer> tm2 = new TreeMap<Long, Integer>();

        for (long j = l; j < l + t; j++) {
            if (stoneL.containsKey(j)) {
                tm2.put(j, stoneL.get(j));
            }
        }


        // 输出
        System.out.println(tm2.get(tm2.firstKey()));
    }

}

把代码一行一行理解,
自己尝试去修改一些数值,
然后反复运行,
这样可以帮助自己理解每一行代码的意思