思路

本质就是最长上升子序列的翻版。删除多少数字得到接龙数列，实际上就是求出序列中最长的接龙数列的长度，要删去的就是剩下数字的个数。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100010;
int a[N],f[N];
int n;

bool check(int i, int j)
{
    int pre = a[j]%10;

    //获取a[i]的首位数字
    int num = a[i];
    while(num >= 10)
    {
        num /= 10;
    }
    int nex = num;
    // printf("%d %d\n",pre,nex);
    if(nex == pre)
        return true;
    else
        return false;
}

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++)
        scanf("%d",&a[i]);

    //初始化
    for(int i = 1; i <= n; i ++)
        f[i] = 1;

    for(int i = 1; i <= n; i ++) //对于每一个a[i]都可以尝试作为尾节点
    {
        for(int j = 1; j < i; j ++) //遍历所有可能的前节点
        {
            if(check(i,j)) //如果满足条件
                f[i] = max(f[j]+1, f[i]); //更新选择最大的
        }
    }

    int res = 0;
    for(int i = 1; i <= n; i ++)
        res = max(res, f[i]);
    printf("%d",n-res);
    return 0;
}