思路
题目问你计算最少从中删除多少个数,可以使剩下的序列是接龙序列,转换一下题目的意思,要想让删除的个数越小,那么我们应该让剩余的尽可能多,于是乎问题就变成了求最长的接龙序列了
直接DP o(n^2)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int s[N];
int st[N],en[N];
int f[N];
int n;
int getst(int x){
while(x>=10){
x/=10;
}
return x;
}
int main(){
cin>>n;
f[0]=0;
for(int i=1;i<=n;i++) f[i]=1;
for(int i=1;i<=n;i++){
cin>>s[i];
st[i]=getst(s[i]);
en[i]=s[i]%10;
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(en[j]==st[i]){
f[i]=max(f[i],f[j]+1);
}
}
}
int k=N+10;
for(int i=1;i<=n;i++) k=min(k,n-f[i]);
cout<<k;
return 0;
}
思路
观察上面代码我们发现,我们每次寻找前面最长的接龙序列的末尾元素实际上必须符和en[j]==st[i],才用进行比较,而其余的遍历都是多余的,而开头和结尾为数字0~9,这样我们只需遍历得到前面以0~9为结尾数字的最大长度,而不是遍历每个元素
优化DP o(n)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int s[N];
int st[N],en[N];
int f[20]; // 表示以i结尾的最长接龙的长度
int n;
int getst(int x){
while(x>=10){
x/=10;
}
return x;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
st[i]=getst(s[i]);
en[i]=s[i]%10;
}
memset(f,0,sizeof f);
for(int i=1;i<=n;i++){
f[en[i]]=max(f[en[i]],f[st[i]]+1);
}
int k=N+10;
for(int i=0;i<10;i++) k=min(k,n-f[i]);
cout<<k;
return 0;
}