蓝桥杯每日一题：接龙数列

题目来源：第十四届蓝桥杯软件赛省赛 B组

对于一个长度为 $K$ 的整数数列: $A_1$, $A_2$ , … , $A_K$ , 我们称之为接龙数列当且仅当 $A_i$ 的首位数字恰好等于 $A_{i-1}$ 的末尾数字 ($2\le i\le K$) . 例如, 12, 23, 35, 56, 61, 11是接龙数列, 12, 23, 34, 56 不受接龙数列, 因为 56 的首位数字不等于 34 的末位数字. 所有长度为 1 的整数数列都是接龙数列

现在给定一个长度为 $N$ 的数列 $A_1,A_2,...,A_N$ , 请你计算最少从中删除多少个数, 可以使得剩下的数列是接龙数列

输入 : 第一行包含一个整数 $N$

第二行包含 $N$ 个整数 $A_1,A_2,...,A_N$

输出 : 一个整数代表答案

Input Sample :

5
11 121 22 12 2023

Output Sample :

1

题目问最少删除多少个数, 我们可以逆转一下思维, 就是算 $N$ 个数最多可以组成多长的接龙数列, 得到的长度 $len$ , $N-len$ 就是我们要的最少删除个数. 我们发现这其实就是最长上升子序列, 完全可以用 DP 来解决. 根据 DP 的知识我们可以知道, 最长上升子序列的状态转移方程应该是:

$f_{i,j}=max(f_{i,j},f_{i-1,j}+1)$

时间复杂度为 $O(N^2)$ . 但是考虑到本题的数据范围 1e5 , 很明显我们不能直接用, 否则会tle. 必须得考虑优化

我们发现, 在这个接龙数列中, 我们只需要考虑数字的首位和末位, 其他的不用考虑. 那么我们只需要 $0\sim 9$ 十个数字就可以表示所有状态 $f[i]$ 表示以 $i$ 结尾的接龙数列. 对于一个数可以看成 $i...j$ ( $i$ 为首位, $j$ 为末位) , 从上一个结尾为 $i$ 的状态转移, 转移方程为

$f[j]=max(f[j],f[i]+1)$

下面给出题解代码, 请注重思考, 不要无脑cv

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
string s;
int res = INT_MAX, n, f[10];

void io() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
}

int main() {
	io();
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s;
		f[s.back() - '0'] = max(f[s.back() - '0'], f[s.front() - '0'] + 1);
	}
	for (int i = 0; i < 9; i++) {
		res = min(res, n - f[i]);
	}
	cout << res << '\n';
	return 0;
}