AcWing 4958. 接龙数列
原题链接
中等
作者:
jh_jju
,
2024-04-05 19:50:14
,
所有人可见
,
阅读 5
接龙序列
由于要前一个数字的末位数字与当前数字的首位数字相同才可以接龙
而数字只有0~9十种情况,故设置一个数组f[10]
f[i]
假设当前数的首位数字为a,末位数字为b
状态表示
集合:以数字i结尾的所有接龙子序列
属性:Max(最长接龙序列)
状态计算
f[b]=max(f[b],f[a]+1);
#include<iostream>
using namespace std;
const int N=100010;
int s[N];
int f[10];
int n;
int get(int x){//得到x的首位数字
int res=x%10;
while(x){
res=x%10;
x/=10;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=1;i<=n;i++){
int a=get(s[i]),b=s[i]%10;
f[b]=max(f[b],f[a]+1);
}
int res=0;
for(int i=0;i<=9;i++)res=max(res,f[i]);
cout<<n-res<<endl;//输出最少需要删除的数的个数
return 0;
}