本文主要是介绍蓝桥杯每日一题:接龙数列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目来源:第十四届蓝桥杯软件赛省赛 B组
对于一个长度为 K K K 的整数数列: A 1 A_1 A1, A 2 A_2 A2 , … , A K A_K AK , 我们称之为接龙数列当且仅当 A i A_i Ai 的首位数字恰好等于 A i − 1 A_{i-1} Ai−1 的末尾数字 ( 2 ≤ i ≤ K 2 \le i \le K 2≤i≤K) . 例如, 12, 23, 35, 56, 61, 11是接龙数列, 12, 23, 34, 56 不受接龙数列, 因为 56 的首位数字不等于 34 的末位数字. 所有长度为 1 的整数数列都是接龙数列
现在给定一个长度为 N N N 的数列 A 1 , A 2 , . . . , A N A_1, A_2,...,A_N A1,A2,...,AN , 请你计算最少从中删除多少个数, 可以使得剩下的数列是接龙数列
输入 : 第一行包含一个整数 N N N
第二行包含 N N N 个整数 A 1 , A 2 , . . . , A N A_1, A_2, ... , A_N A1,A2,...,AN
输出 : 一个整数代表答案
Input Sample :
5 11 121 22 12 2023
Output Sample :
1
题目问最少删除多少个数, 我们可以逆转一下思维, 就是算 N N N 个数最多可以组成多长的接龙数列, 得到的长度 l e n len len , N − l e n N - len N−len 就是我们要的最少删除个数. 我们发现这其实就是最长上升子序列, 完全可以用 DP 来解决. 根据 DP 的知识我们可以知道, 最长上升子序列的状态转移方程应该是:
f i , j = m a x ( f i , j , f i − 1 , j + 1 ) f_{i, j} = max(f_{i, j}, f_{i - 1, j} + 1) fi,j=max(fi,j,fi−1,j+1)
时间复杂度为 O ( N 2 ) O(N^2) O(N2) . 但是考虑到本题的数据范围 1e5 , 很明显我们不能直接用, 否则会tle. 必须得考虑优化
我们发现, 在这个接龙数列中, 我们只需要考虑数字的首位和末位, 其他的不用考虑. 那么我们只需要 0 ∼ 9 0\sim9 0∼9 十个数字就可以表示所有状态 f [ i ] f[i] f[i] 表示以 i i i 结尾的接龙数列. 对于一个数可以看成 i . . . j i...j i...j ( i i i 为首位, j j j 为末位) , 从上一个结尾为 i i i 的状态转移, 转移方程为
f [ j ] = m a x ( f [ j ] , f [ i ] + 1 ) f[j] = max(f[j], f[i] + 1) f[j]=max(f[j],f[i]+1)
下面给出题解代码, 请注重思考, 不要无脑cv
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
string s;
int res = INT_MAX, n, f[10];void io() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
}int main() {io();cin >> n;for (int i = 1; i <= n; i++) {cin >> s;f[s.back() - '0'] = max(f[s.back() - '0'], f[s.front() - '0'] + 1);}for (int i = 0; i < 9; i++) {res = min(res, n - f[i]);}cout << res << '\n';return 0;
}
这篇关于蓝桥杯每日一题:接龙数列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!