接龙序列

Problem

对于一个长度为 $K$ 的整数数列：$A_1,A_2,...,A_K$，我们称之为接龙数列当且仅当 $A_i$ 的首位数字恰好等于 $A_{i−1}$ 的末位数字 $(2≤i≤K)$。

例如 $12,23,35,56,61,11$ 是接龙数列；$12,23,34,56$ 不是接龙数列，因为 $56$ 的首位数字不等于 $34$ 的末位数字。

所有长度为 $1$ 的整数数列都是接龙数列。

现在给定一个长度为 $N$ 的数列 $A_1,A_2,...,A_N$，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2,...,A_N$。

输出格式

一个整数代表答案。

数据范围

对于 $20\%$ 的数据，$1≤N≤20$。
对于 $50\%$ 的数据，$1≤N≤10000$。
对于 $100\%$ 的数据，$1≤N≤10^5$，$1≤A_i≤10^9$。所有 $A_i$ 保证不包含前导 $0$。

输入样例：

5
11 121 22 12 2023

输出样例：

1

样例解释

删除 $22$，剩余 $11,121,12,2023$ 是接龙数列。

Solutions

题目转换：

+ 题目描述说“请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？”，“最少删除”即为求最长的接龙序列。
+ 朴素版就是借鉴 $LIS$ 朴素版的做法。
+ 优化版是每次找第 $i$ 个数之前的数，其实只需要用到尾字母 $r$，所以只需要开一个数组f[N],其中f[i]表示尾字母是 $i$ 的数的接龙序列的最大长度。（具体看代码，代码非常优美）

AC Code

#### 朴素版 $O(n^2)$ $TLE$

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int f[N],h[N],r[N];

int main()
{
    int n;
    cin>>n;


    for(int i=0;i<n;++i)
    {
        string str;
        cin>>str;
        h[i]=str.front()-'0',r[i]=str.back()-'0';//记录第i个数的首字母和尾字母
    }
    for(int i=0;i<n;++i)    f[i]=1;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<i;++j)
        {
	        //找第i个数之前的尾字母数是h的数,可以借到它的后面
            if(r[j]==h[i])  f[i]=max(f[i],f[j]+1);
        }
    }

    int res=0;
    for(int i=0;i<n;++i)    res=max(res,f[i]);
    cout<<n-res<<endl;

    return 0;
}

#### 优化版 $O(n\log{n})$

#include <bits/stdc++.h>

using namespace std;

const int N=100;

int f[N];//f[i]表示当前以数字i结尾的最长序列长度

int main()
{
    int n;
    cin>>n;

    int maxLen=0;//最长接龙序列长度
    for(int i=0;i<n;++i)
    {
        string str;
        cin>>str;
        int h=str.front()-'0';//首字母
        int r=str.back()-'0';//尾字母
        f[r]=max(f[r],f[h]+1);//当前这数字的应该接到尾字母是h的数字后面
        //特殊情况,如果找不到尾字母是h的数,那么f[r]=1(f[r]=f[h]+1,此时f[h]==0)
        //f[r]更新用max去更新,不要写成f[r]=f[h]+1
        maxLen=max(maxLen,f[r]);
    }
    cout<<n-maxLen<<endl;

    return 0;
}

##### Note

状态表示：f[i]表示以数字i结尾的接龙序列的最长长度
状态转移：f[r]=max(f[r],f[h]+1)，其中h为str_num的首字母，r为str_num的尾字母

+ 比如字符串23，f[3]有两个选择
+ f[3]=f[2]+1：23接到xx2的后面
+ f[3]=f[3]：f[3]可以由其他字符串表示，以数字3结尾的接龙序列的最后一个字符串不一定是23，也可以是其他的字符串