第十四届蓝桥杯. 接龙数列(线性DP)

对于一个长度为 K 的整数数列：A1,A2,...,AK，我们称之为接龙数列当且仅当 A i 的首位数字恰好等于 A i−1 的末位数字 (2≤i≤K)。例如 12,23,35,56,61,11 是接龙数列；12,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。现在给定一个长度为 N 的数列 A1,A2,...,AN，请你计算最少从中删除多少个数，可以使剩下的序列是

文章共510字 · 阅读需要大约2分钟

一键AI生成摘要，助你高效阅读

问答

陈进士学习

3299人浏览 · 2023-05-01 08:30:06

陈进士学习 · 2023-05-01 08:30:06 发布

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

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

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

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

输入格式

第一行包含一个整数 N。

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

输出格式

一个整数代表答案。

数据范围

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

输入样例：

5
11 121 22 12 2023

输出样例：

样例解释

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

解析：dp[ i ][ j ]为前 i 个数中，以 j 结尾的最长接龙序列的长度。

第 i 个数的首尾分别为 a，b

1. 如果不加上第 i 个数，则dp[ i ][ b ] = dp[ i-1 ][ b ]

2. 如果加上第 i 个数，则dp[ i ][ b ] = max( dp[ i-1 ][ b ] , dp[ i-1 ][ a ]+1)

同时可以优化，去掉第一维。

代码：

#include<bits/stdc++.h>
using namespace std;
int dp[10],n,res;
int main(){
	cin>>n;
    for(int i=0;i<n;i++) {
        string s;
		cin>>s;
        int a=s[0]-'0',b=s.back()-'0';
        dp[b]=max(dp[b],dp[a]+1);
		res=max(res,dp[b]);
    }
    cout<<n-res<<endl;
    return 0;
}