题解 | #半夏老师的课堂时间#

第四道题 也是一个模板题

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int  l[N],r[N],f[N],g[N];
int main() {
	int n;cin>>n;
	for(int i=0;i<n;i++){
		string str;cin>>str;//接受每个数字
		l[i]=str.front()-'0';//将输入数字的第一位 从字符转化为int型
		r[i]=str.back()-'0';//同理,将最后一位从字符转化为int型
	}
	int mx=0;//mx定义的就是最大的数列长度
	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]]);
	}
	for(int i=0;i<n;i++)mx=max(mx,f[i]);
	cout<<n-mx;//那么删掉的最小长度,就是总长度减去数列最长长度
return 0;
}