AcWing 4958. 接龙数列
原题链接
中等
作者:
星殇
,
2024-02-24 17:18:28
,
所有人可见
,
阅读 20
#include <bits/stdc++.h>
#define PI acos(-1)
#define all(a) (a).begin(), (a).end()
#define erjinzhi(n) __builtin_popcountll(n);
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
// #pragma GCC optimize(2,"Ofast","inline")
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
const char nl = '\n';
const int N = 1e5 + 10;
string a[N];
int f[N]; // 集合表示f[i]表示以第i个数字为结尾的接龙数列的集合,属性为max
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
f[a[i].back() - '0'] = max(f[a[i].back() - '0'],f[a[i].front() - '0'] + 1);
int mx = 0;
for (int i = 1; i <= 9; ++i)
mx = max(mx, f[i]);
cout << n - mx;
return 0;
}