AcWing 4958. 接龙数列
原题链接
中等
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int l[N],r[N];
int g[N];
int f[N];
int main(){
int n;
cin >> n;
for(int i =0; i < n; i++){
char s[10];
cin >> s;
l[i] = s[0] - '0', r[i] = s[strlen(s) - 1] - '0';
}
int res = 0;
for(int i =0; i < n; i++){
f[i] = 1;
f[i] = max(f[i], g[l[i]] + 1);//以当前这个值的左侧为结尾的前面的数字的值
g[r[i]] = max(f[i], g[r[i]]);//设置以当前这个值的右侧为结尾的数字的值
res = max(res,f[i]);
}
cout << n - res;
}