P9242 [蓝桥杯 2023 省 B] 接龙数列

P9242 [蓝桥杯 2023 省 B] 接龙数列 - 洛谷

题目描述

对于一个长度为 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​。

输出格式

一个整数代表答案。

输入输出样例

输入 #1	输出 #1
5 11 121 22 12 2023	1

说明/提示

【样例说明】
删除 22，剩余 11,121,12,2023 是接龙数列。

【评测用例规模与约定】
对于 20% 的数据，1≤N≤20。

对于 50% 的数据，1≤N≤104。

对于 100% 的数据，1≤N≤105，1≤Ai​≤1010。所有 Ai​ 保证不包含前导 0。

蓝桥杯 2023 省赛 B 组 E 题。

思路：
代码：
 

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int mem[MAXN][11]; 
int num[MAXN];
int n;
// 获取数字的首位数字
int get_First(int num) 
{string s = to_string(num);int f = s[0] - '0';return f;
}// 获取数字的末位数字
int get_Last(int num) 
{return num % 10;
}
int dfs(int x,int last)
{if (x > n)//处理完全部数字 {return 0;}if (mem[x][last + 1] != -1) //记忆化数组 {return mem[x][last + 1];}int first = get_First(num[x]);  // 获取当前数字的首位数字int curLast = get_Last(num[x]);    // 获取当前数字的末位数字int notchoose = 1e9,choose = 1e9;// 不选择当前数字，删除数字个数加 1notchoose = dfs(x + 1, last) + 1;// 选择当前数字if (last == -1 || first == last) // 判断是否满足接龙条件{choose = dfs(x + 1, curLast);}// 取选择和不选择两种情况的最小值mem[x][last + 1] = min(choose, notchoose);return mem[x][last + 1];
}
int main(void)
{cin >> n;for(int i = 1 ; i <= n ; i++)cin >> num[i];memset(mem, -1, sizeof(mem));int ans = dfs(1,-1);//参数为第x位数字，前一个数字末尾数字为-1 cout << ans;	return 0;}