本文主要是介绍蓝桥杯十四届c/c++省赛：飞机降落、接龙数列（Java版可AC代码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
飞机降落
题目描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早
可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T，代表测试数据的组数。
对于每组数据，第一行包含一个整数 N。
以下 N 行，每行包含三个整数：Ti，Di 和 Li。
输出格式
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。
样例输入
复制
2 3 0 100 10 10 10 10 0 2 20 3 0 10 20 10 10 20 20 10 20
样例输出
复制
YES NO
提示
对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。
对于第二组数据，无论如何安排，都会有飞机不能及时降落。
对于 30% 的数据，N ≤ 2。
对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti , Di , Li ≤ 105。
代码
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;public class Main{static Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));// 快速输入 比普通Scanner输入效率更快 static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));// 快速输出 本题运行总时长为：403mspublic static void main(String[] args) {int T = in.nextInt();for(int i = 0; i < T; i++) {int n = in.nextInt();int[][] tdl = new int[n][4];// 多出一列用于等等回溯时，用作标记是否使用过for(int j = 0; j < n; j++) {tdl[j][0] = in.nextInt();tdl[j][1] = in.nextInt();tdl[j][2] = in.nextInt();}// 调用回溯函数if(backtracking(tdl, n, 0)) {out.println("YES");}else {out.println("NO");}}out.close();}// 由于还有不满足条件的情况，所以回溯函数返回值为boolean类型（总结：即需要返回两种结果时，返回值用boolean）private static boolean backtracking(int[][] tdl, int count, int time) {if(count == 0) {return true;}// tdl.length就是行数，tdl[0].length表示列数for(int i = 0; i < tdl.length; i++) {if(time > tdl[i][0] + tdl[i][1] || tdl[i][3] == 1) {// tdl[i][3] == 1表示上一层递归使用过continue;}
// int temp = time;count--;tdl[i][3] = 1;
// time = Math.max(time, tdl[i][0]) + tdl[i][2];// 这个也可以直接作为下次递归的time位置的参数，回溯的时候，就不用修改time了if(backtracking(tdl, count, Math.max(time, tdl[i][0]) + tdl[i][2])) {return true;}else {// 回溯：count++;tdl[i][3] = 0;
// time = temp; 参数调用的是Math.max(time, tdl[i][0]) + tdl[i][2]，就不用修改time了}}return false;}
}这题网上大多都叫DFS（深度优先），我个人更喜欢叫回溯。
好久没写回溯的题了，代码实现的时候有点生疏，关键在于判断退出条件，还有用boolean作为返回参数，可以符合题目要求输出两种类型的结果（YES/NO），以及更新time，可以直接把更新的time传入参数中，这样回溯就更简洁了，而time的更新则是要确保：
如果第一架飞机就从10才能起飞，那么time还是穿time+Li吗？
理解一下这个问题就知道为什么time = Math.max(time, tdl[i][0]) + tdl[i][2])了。
接龙数列
题目描述
对于一个长度为 K 的整数数列：A1, A2, . . . , AK，我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。
例如 12, 23, 35, 56, 61, 11 是接龙数列；12, 23, 34, 56 不是接龙数列，因为 56的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A1, A2, . . . , AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, . . . , AN。
输出格式
一个整数代表答案。
样例输入
复制
5 11 121 22 12 2023
样例输出
复制
1
提示
删除 22，剩余 11, 121, 12, 2023 是接龙数列。
对于 20% 的数据，1 ≤ N ≤ 20。
对于 50% 的数据，1 ≤ N ≤ 10000。
对于 100% 的数据，1 ≤ N ≤ 105，1 ≤ Ai ≤ 109。所有 Ai 保证不包含前导 0。
代码
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;public class Main{static Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));// 769msstatic PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static void main(String[] args) {// 动态规划：// 1. 确定dp:dp[i]表示以i结尾的接龙数列的最大长度int max = 0;int n = Integer.parseInt(in.nextLine());String[] nums = in.nextLine().split(" ");int[] dp = new int[n];/* 2. a:nums[i]的首位，b:是nums[i]的末位* dp[b]表示nums[i]中以b结尾的接龙数列最大长，dp[a]表示nums[i - 1]中以a结尾的接龙数列最大长* * dp[b] = Math.max(dp[b], dp[a] + 1);*/ for(int i = 0; i < n; i++) {int endNumber = nums[i].charAt(nums[i].length() - 1) - '0';int startNumber = nums[i].charAt(0) - '0';dp[endNumber] = Math.max(dp[endNumber], dp[startNumber] + 1);// 不需要管i，只需要管每个数字的首末位数就行，因为能否组成接龙数列的就看这两个数字，不是看第i个数字与i-1的关系，// 而是看当前数字的首位，是否在之前计算过，如果当前数字首位之前计算过，直接加上当前数字这个“1”，就行，即：dp[startNumber] + 1if(dp[endNumber] > max) {max = dp[endNumber];}}out.print(n - max);out.close();}
}还是非常抽象的，建议根据dp[i]的含义，以及for循环，还有递推公式dp[b] = Math.max(dp[b], dp[a] +1)模拟一下过程才能更好理解吧
这篇关于蓝桥杯十四届c/c++省赛：飞机降落、接龙数列（Java版可AC代码）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
