题目描述

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

提示

删除 22，剩余 11, 121, 12, 2023 是接龙数列。
对于 20% 的数据，1 ≤ N ≤ 20。
对于 50% 的数据，1 ≤ N ≤ 10000。
对于 100% 的数据，1 ≤ N ≤ 105，1 ≤ Ai ≤ 109。所有 Ai 保证不包含前导 0。

暴力DP 50%

求删去i个数，剩下接龙数列
实则为求最长的接龙数列长度i，n-i即为答案
dp[i]表示以第i个数结尾的最长接龙数列长度，
若在前面找到第j个数与第i个数形成接龙数列，则
dp[i] = max(dp[i], dp[j] + 1)
遍历数列即可

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, dp[N], ans = 1;
string a[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[i] = 1;
    }
    // dp[i]表示以第i个数结尾的最长接龙数列长度
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            // 若a[i]的首位数字等于a[j]的末位数字
            if (a[i][0] == a[j][a[j].size() - 1])
                // 不接还是接，取最大值
                dp[i] = max(dp[i], dp[j] + 1);
        }
        // 记录最长接龙数列长度
        ans = max(ans, dp[i]);
    }
    ans = n - ans;
    cout << ans;
    return 0;
}

优化DP 100%

观察规律，我们发现
对于数字abcd，以d结尾的最长接龙数列长度 只与 以a结尾的最长接龙数列长度 有关
即
dp[d]只与dp[a]有关
或
dp[d] = max(dp[d], dp[a] + 1)
(该式与前式不同，前式的dp[i]是指第i个数，这样的数有n个；而该式的dp[d]的d或a是指数字，数字只有10个)
因此，只需要遍历一遍数列，直接计算即可

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, dp[10] = {}, ans = 1;
    string s;
    cin >> n;
    // dp[i] 表示以 i 结尾的最长接龙数列的长度
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        // 取出首和尾字符
        int first = s[0] - '0', last = s[s.size() - 1] - '0';
        // dp[d] = max(dp[d], dp[a] + 1)`
        dp[last] = max(dp[last], dp[first] + 1);
        // 记录最长接龙数列长度
        ans = max(ans, dp[last]);
    }
    ans = n - ans;
    cout << ans;
    return 0;
}