3152 问题 C: 蓝桥杯2023年第十四届省赛真题-接龙数列

时间限制: 1s 内存限制: 256MB 提交: 14663 解决: 3566
题目描述
对于一个长度为 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。


比赛公告

2023年蓝桥杯比赛大学B组省赛题目以及团队成员皆可参加员无需密码,其他人需要密码进入比赛。