接龙序列(动态规划c++实现)

题目

对于一个长度为 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。

输出格式

一个整数代表答案。

样例

输入样例：
5
11 121 22 12 2023

输出样例：
1

代码

#include<iostream>
#include<string.h>
using namespace std;
const int N = 1e5+10;
int l[N],r[N],g[11],f[N];
int n;

int getLast(int x){
    return x%10;
}

int getFirst(int x){
    string s = to_string(x);
    int first = (s[0]-'0');
    return first;
}

int main(){
    scanf("%d",&n);
    
    for(int i=1;i<=n;i++) {
        int x;
        scanf("%d",&x);
        l[i] = getFirst(x);
        r[i] = getLast(x);
    }
    int res = 0;
    for(int i=1;i<=n;i++){
        f[i] = 1;
        f[i] = max(f[i],g[l[i]]+1);
        g[r[i]] = max(g[r[i]],f[i]);
        res = max(res,f[i]);
    }
    
    printf("%d",n-res);
    
}