蓝桥杯2023年第十四届省赛真题-接龙数列 – C语言网 (dotcpp.com)
我们要求最少删除多少个数,可以使剩下的序列是接龙序列。
那么找到一条最长的接龙数列即可求出最少删除的个数。
运用动态规划的思想,从前往后挨个考虑每个数字。
一个前缀为6的数字能且只能和前面任何一个后缀为6的数字相接,
我们只要选择已知长度最长的那一个即可,也就是56。
用一个长度为10的数组a【10】表示每种后缀已知的最大长度,
a【9】= max( a【6】+ 1,a【9】);
a【后缀】= max( a【前缀】+ 1,a【后缀】)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define L "%lld"
ll a1[10];
int main() {
ll n;
scanf(L, &n);
for (int i = 1; i <= n; i ++) {
ll a;
scanf(L, &a);
ll l, r;
r = a % 10;
while (a) {
l = a % 10;
a /= 10;
}
a1[r] = max(a1[r], a1[l] + 1);
}
ll ma = 0;
for (int i = 0; i <= 9; i ++) {
ma = max(ma, a1[i]);
}
printf(L, n - ma);
return 0;
}
最后再找一下哪个后缀的数列最长。
版权声明:本文为博主作者:yeying075原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/yeying075/article/details/130047472