蓝桥杯2022与2023年省赛专题练习_问题C

提交: 14663 解决: 3566

题目描述

对于一个长度为 K 的整数数列：A₁, A₂, . . . , A_K，我们称之为接龙数列当且仅当 A_i 的首位数字恰好等于 A_i−1 的末位数字 (2 ≤ i ≤ K)。

例如 12, 23, 35, 56, 61, 11 是接龙数列；12, 23, 34, 56 不是接龙数列，因为 56的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。

现在给定一个长度为 N 的数列 A₁, A₂, . . . , A_N，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入

第一行包含一个整数 N。

第二行包含 N 个整数 A₁, A₂, . . . , A_N。

输出

一个整数代表答案。

样例输入

5
11 121 22 12 2023

样例输出

提示

删除 22，剩余 11, 121, 12, 2023 是接龙数列。

对于 20% 的数据，1 ≤ N ≤ 20。

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

对于 100% 的数据，1 ≤ N ≤ 10⁵，1 ≤ A_i≤ 10⁹。所有 A_i 保证不包含前导 0。

本次比赛为蓝桥杯2022和2023年省赛C++题目，同时如果大家要加强练习，可以在该网站上其他对应科目和语言进行练习，加强练习，下学期省赛一定能取得好的成绩！加油！