接龙序列
题目 接龙数列
思路分析
一眼最长上升子序列模型
发生了点变化 在于
之前i是由小于它的j推过来 现在i由在它前面的 最后一个字符等于它的第一个字符的j推过来
把每个数的首位和末尾存下来 朴素做法直接就出来了
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N];
int first[N],last[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
string x;
cin>>x;
first[i]=x[0]-'0';
last[i]=x.back()-'0';
}
int res=0;
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(last[j]==first[i])
f[i]=max(f[i],f[j]+1);
}
res=max(res,f[i]);
}
cout<<n-res;
return 0;
}
这个做法的时间复杂度为n^2
只能过一半数据 还得想办法优化
用g[10];存储第i个数字之前以末尾数字k(0 <= k <= 9)为结尾的接龙序列的max 即g[k]表示在第i个数字以前,为k为末尾的接龙序列的最大长度
那么就可以省去一层循环
接龙序列
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N];
int first[N],last[N];
int g[N];//g[k]表示在第i个数字以前,为k为末尾的接龙序列的最大长度
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
string x;
cin>>x;
first[i]=x[0]-'0';
last[i]=x.back()-'0';
}
int res=0;
for(int i=1;i<=n;i++){
f[i]=1;
f[i]=max(f[i],g[first[i]]+1);//只关心以first[i]为结尾的数字
g[last[i]]=max(g[last[i]],f[i]);//第i个数字的末尾为last[i],更新g[]
res=max(res,f[i]);
}
cout<<n-res;
return 0;
}
💬 评论