题目描述

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

思路:

找到最长的接龙数列的长度 len, 那么 n - len 就是最小操作数。

可以使用 dp 找到最长的接龙数列

首先定义状态所代表的子集:

f[i][j]: 在前 i 个数中结尾数字为 j 的所有数列

定义子集的属性为最大长度。

接下来我们推导状态转移:

对于数字 a, 我们用 a.first 表示其首位数字, b.first 表示其末尾数字, 假设我们当前集合准备选取数字 k:

那么对于数字 k 这个对象, 有选和不选两种情况

如果不选的话: f[i][k.second] = f[i - 1][k.second]

如果选的话: f[i][k.second] = f[i - 1][k.first]

于是有 f[i][k.second] = max(f[i - 1][k.second], f[i - 1][k.first])

由于我们要取 f[n][0] ~ f[n][9] 的最大值, 那么需要在每次循环前可以先计算出不选时的答案 f[i][j]=f[i- 1][j] (否则会全部 WA 暴零):