Responsive image

问题 2860 --试题 E: 接龙数列(DP最长上升子序列+二分优化)

2860: 试题 E: 接龙数列(DP最长上升子序列+二分优化)

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

对于一个长度为 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 ≤ A≤ 109。所有 Ai 保证不包含前导 0

来源

[提交][状态]
ACM算法攻关部