【DP】第十四届蓝桥杯省赛C++ B组《接龙数列》（C++）

【题目描述】

对于一个长度为 K 的整数数列：A1,A2,...,AK，我们称之为接龙数列当且仅当  的首位数字恰好等于  的末位数字 (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≤10的5次方，1≤Ai≤10的9次方。所有 Ai 保证不包含前导 0。

【输入样例】

【输出样例】

【样例解释】

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

【代码】

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

using namespace std;

const int N = 100010;

int n;
int g[10];

int main()
{
    scanf("%d", &n);

    int res = 0;
    char num[20];
    for (int i = 0; i < n; i ++ )
    {
        scanf("%s", num);
        int l = num[0] - '0', r = num[strlen(num) - 1] - '0';
        int f = max(1, g[l] + 1);
        g[r] = max(g[r], f);
        res = max(res, f);
    }

    printf("%d\n", n - res);
    return 0;
}