第十四届蓝桥杯省赛C/C++ 大学 B 组 第五题 接龙数列

本题是一个比较基础的线性dp的题目。

关于题目中所给的N个整数A1，A2.....AN，我们可以通过输入字符串的方式得到第一个值a和某尾的值b，对于以值b结尾的整数序列的最大值，我们只需用以值a结尾的整数序列最大值+1即可。最后遍历结尾的可能值a[0]-a[9]，找出最大值即可

代码如下：

#include<iostream> #include<vector> using namespace std; int a1[100010]; typedef struct xx { int q, h; }val; vector<val> p; int idx; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { string s1; cin >> s1; int a, b; a = s1[0] - '0'; b = s1[s1.size() - 1] - '0'; a1[b] = max(a1[b], a1[a] + 1); } int res = 0; for (int i = 0; i < 10; i++) { res = max(res, a1[i]); } cout << n-res << endl; return 0; }