接龙序列
我们称序列中\(a_i\)的首位数字恰好是\(a_{i-1}\)的末尾数字，这样的序列叫做接龙序列，比如
12 23 35 57,所有长度为1的整数序列都是接龙序列，现在给定一个长度为\(n\)的序列\(a\)，请你计算最少从中删除多少个数，可以使得剩下的序列是接龙序列
题解：\(DP\)
根据题目我们可以转化题意为：求出最长的接龙序列，那么答案就是\(n-\)最长接龙序列的长度
这道题显然和最长上升子序列问题比较像，所以我们按照最长上升子序列的思路走；
状态表示：\(f[i]\)：以第\(i\)个数结尾的最长接龙序列的长度
状态属性：\(MAX\)
状态计算：我们只要找到前面所有末尾数字和第\(i\)个数的首位数字相同的数\(a_j\)，接在它的后面即可
\[f[i] = max(f[i],f[j]+1),j<i\ \wedge r[j] = l[i] \] 显然复杂度是\(O(n^2)\)的，我们考虑进行优化
状态优化：因为第\(i\)个数只能接在末尾数字\(x\)和第\(i\)个数首位数字相等的数后面，所以我们实际上可以开一个辅助 数组\(g\)来存放前\(i-1\)个数中以\(x\)结尾的\(f[j]\)的最大值，即
\[g[x] = max(g[x],f[j]),j<i,r[j]=x\\ f[i] = max(f[i],g[x]+1) \] 那么复杂度被优化到了\(O(n)\)
状态初始：\(f[i] = 1\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n;
int g[N], f[N];
int l[N], r[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
string s;
cin >> s;
l[i] = s[0] - '0';
r[i] = s[s.size() - 1] - '0';
}
int ans = 0;
for (int i = 1; i <= n; ++i)
{
f[i] = 1;
f[i] = max(f[i], g[l[i]] + 1);
g[r[i]] = max(g[r[i]], f[i]);
ans = max(ans, f[i]);
}
cout << n - ans << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}