蓝桥杯接龙数列（动态规划）

蓝桥杯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;
}

最后再找一下哪个后缀的数列最长。