AcWing 4958. 接龙数列
原题链接
中等
作者:
ruomusu
,
2024-04-03 21:29:45
,
所有人可见
,
阅读 2
import java.util.*;
public class Main{
static int N = 100010, n;
static int res = Integer.MAX_VALUE;
static int[][] f = new int[N][10]; // f[i][j] 表示前i个数最长子序列中最后一个数的末位数是j的删除数量
static int[] g = new int[N]; // g[]存数组
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 1; i <= n; i ++){
g[i] = sc.nextInt(); // 从1开始时因为后面有i - 1,从0开始会超过范围不太好
}
for(int i = 0; i <= 9; i ++){
f[0][i] = 0; // 一个数都没有不管以0~9之间的什么数结尾都为0
}
for(int i = 1; i <= n; i ++){
// 如果第i个数字不选
for(int j = 0; j <= 9; j ++){
f[i][j] = f[i - 1][j] + 1;
}
// 将如果选和不选进行对比
f[i][getLast(g[i])] = Math.min(f[i - 1][getFirst(g[i])], f[i][getLast(g[i])]);
}
for(int i = 0; i <= 9; i ++){
res = Math.min(res, f[n][i]);
}
System.out.println(res);
}
static int getLast(int last){
return last % 10;
}
static int getFirst(int first){
int num = 0;
while(first > 0){
num = first % 10;
first = first / 10;
}
return num;
}
}
// dfs递归的小感悟:
// 做题多了,有时候对于递归的概念就开始模糊,所以需要重新从源头来把握思想
// 对于递归,第一个要点是有结束判定,否则会一直往下递归这个很好理解
// 第二个就是递归最底层出来之后会怎么样,由于有的代码有多个递归,一来而来就会混淆不知道接下来怎么运行,就会想哪种情况会不会被忽略,但其实不会
// 就这题而言,有两个递归,第一个是选第u个数进行递归,第二个是不选第u个数递归,那么到递归终点后会从哪里出来呢?情况会不会都包括了呢?
// 把握一个要点与一个测评方法,首先递归从哪个入口进去的,那么return后,就会从哪个递归入口出来,并继续执行下面的代码,这个毫无疑问
// 根据这一个要点就有一个判断是否考虑全部情况的测评方法,首先根据要点:如果继续执行下面的代码,那么此递归就相当于没有进去,并且没进去就表示
// 此时的数值状态和进入递归前的初始状态一样,换句话说,你可以直接把这个递归代码删除,沿着递归的下一行去执行代码,如果把dfs(u + 1, cnt + 1, last)
// 去掉之后,此时if的下一行没有语句,就会退出if判断,执行下一段语句,即进入下一个递归,那这时就是没有选这个数字的下一个递归情况,即dfs(1, 0, -1)当时的困惑在于
// 既然强制进入了第一个递归,那怎么才会轮到不进入第一个递归的情况,这时候用测评方法就很好解释了,直接把第一个递归代码删除,那么就会
// 执行第二个递归代码,第二个递归代码恰好就是不选的情况,所以将所有的情况都包括进去了。
// dfs递归暴力解 拿小分
public class Main{
static int N = 100010, n, ans; // 存放了多少值,以及最多选多少个数
static int[] g = new int[N]; // 存原来的数组
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0; i < n; i ++){
g[i] = sc.nextInt();
}
dfs(0, 0, -1);
System.out.println(n - ans);
}
static int getLast(int last){
return last % 10;
}
static int getFirst(int first){
int num = 0;
while(first > 0){
num = first % 10;
first = first / 10;
}
return num;
}
static void dfs(int u, int cnt, int last){
if(u == n){
ans = Math.max(ans, cnt);
return;
}
if(cnt + n - u <= ans) return;
// 如果选第u个数
if(last == -1 || getLast(last) == getFirst(g[u])){
dfs(u + 1, cnt + 1, g[u]); // 此时的g[u]就是下一轮的last,因为下一轮的first取的是此时传入的g[u + 1]的值,慢半拍就行
}
dfs(u + 1, cnt, last);
}
}