---
title: "接龙序列"
created: 2025-11-28
tags:
  - 算法
---

# 接龙序列

## 题目 [接龙数列](https://www.acwing.com/problem/content/description/4961/)

![[image-031eb49b.png]]

## 思路分析

一眼最长上升子序列模型

发生了点变化 在于

之前i是由小于它的j推过来 现在i由在它前面的 最后一个字符等于它的第一个字符的j推过来

把每个数的首位和末尾存下来 朴素做法直接就出来了

![[image-7d5a6bd5.png]]

```cpp
#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为末尾的接龙序列的最大长度

那么就可以省去一层循环

接龙序列

## 代码实现

```cpp
#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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[拦截导弹|拦截导弹]] 🏠 [[00-刷题理模型]] ➡️ [[最短编辑距离|最短编辑距离]]