题目描述

对于一个长度为K的整数数列：A1,A2,…,AK，我们称之为接龙数列当且仅当
Ai的首位数字恰好等于 Ai−1的末位数字 (2≤i≤K)。

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

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

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

输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…,AN。

输出格式
一个整数代表答案。

数据范围
对于 20% 的数据，1≤N≤20。
对于 50% 的数据，1≤N≤10000。
对于 100% 的数据，1≤N≤105，1≤Ai≤109。所有 Ai 保证不包含前导 0。

样例

5
11 121 22 12 2023

算法(动态规划) $O(n)$

思路:

状态表示:
    其中f[i]表示以第i个数结尾的最终序列的最长序列个数，
    则此时的最小删除个数即为i - f[i] + n - i = n - f[i]。
    最后只需要对所有的n - f[i]取最小值即可。

本想法关键在于如何计算f[i]

状态计算:
    由于f[i]一定包含第i个数，且第i个数一定要接在头部和前方数字尾部相同的点后面。
    则f[i] = max(f[j1], f[j2] ... ) + 1， 
    其中j等是指结尾与第i个数首部相同的点
    故可以用一个position数组记录以每个数结尾的在前方已经出现过的长度的位置
    ，即可将状态计算过程降为O(1)。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010, M = 20;
int f[N];//状态表示
int max_p[M];//记录以1-9每个点结尾的长度的最大值
int position[M];//记录以1-9每个点的结尾的长度的最大值位置
int start[N], ed[N];//记录每个点的头和尾
int n;
int main()
{
    cin >> n;
    f[1] = 1;
    int ans = n - 1;
    for (int i = 1; i <= n; i ++ )
    {
        string s;
        cin >> s;
        start[i] = s.front() - '0';
        ed[i] = s.back() - '0';
        if (i > 1) f[i] = f[position[start[i]]] + 1;//状态计算
        if (f[i] > max_p[ed[i]])
        {
            max_p[ed[i]] = f[i];
            position[ed[i]] = i;
        }//如果当前点的长度大于该尾数长度的最大值，则将最大值及其位置更新到该点
        ans = min(ans, n - f[i]);//计算答案
    }
    cout << ans << endl;

    return 0;
}