电白区建设局网站,网页制作背景图代码,深圳阿里网站设计公司,深圳网站建设流程[蓝桥杯 2023 省 B] 接龙数列
题目描述
对于一个长度为 K K K 的整数数列#xff1a; A 1 , A 2 , … , A K A_{1},A_{2},\ldots,A_{K} A1,A2,…,AK#xff0c;我们称之为接龙数列当且仅当 A i A_{i} Ai 的首位数字恰好等于 A i − 1 A_{i-1} Ai−1 的末位数字…[蓝桥杯 2023 省 B] 接龙数列
题目描述
对于一个长度为 K K K 的整数数列 A 1 , A 2 , … , A K A_{1},A_{2},\ldots,A_{K} A1,A2,…,AK我们称之为接龙数列当且仅当 A i A_{i} Ai 的首位数字恰好等于 A i − 1 A_{i-1} Ai−1 的末位数字 2 ≤ i ≤ K 2 \leq i \leq K 2≤i≤K。
例如 12 , 23 , 35 , 56 , 61 , 11 12,23,35,56,61,11 12,23,35,56,61,11 是接龙数列 12 , 23 , 34 , 56 12,23,34,56 12,23,34,56 不是接龙数列因为 56 56 56 的首位数字不等于 34 34 34 的末位数字。所有长度为 1 1 1 的整数数列都是接龙数列。
现在给定一个长度为 N N N 的数列 A 1 , A 2 , … , A N A_{1},A_{2},\ldots,A_{N} A1,A2,…,AN请你计算最少从中删除多少 个数可以使剩下的序列是接龙序列
输入格式
第一行包含一个整数 N N N。
第二行包含 N N N 个整数 A 1 , A 2 , … , A N A_{1},A_{2},\ldots,A_{N} A1,A2,…,AN。
输出格式
一个整数代表答案。
样例 #1
样例输入 #1
5
11 121 22 12 2023样例输出 #1
1提示
【样例说明】
删除 22 22 22剩余 11 , 121 , 12 , 2023 11,121,12,2023 11,121,12,2023 是接龙数列。
【评测用例规模与约定】
对于 20 % 20 \% 20% 的数据 1 ≤ N ≤ 20 1 \leq N \leq 20 1≤N≤20。
对于 50 % 50 \% 50% 的数据 1 ≤ N ≤ 1 0 4 1 \leq N \leq 10^4 1≤N≤104。
对于 100 % 100 \% 100% 的数据 1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^{5} 1≤N≤105 1 ≤ A i ≤ 1 0 9 1 \leq A_{i} \leq 10^{9} 1≤Ai≤109。所有 A i A_{i} Ai 保证不包含前导 0。
蓝桥杯 2023 省赛 B 组 E 题。 思路
使用一维数组a来存储输入的序列每个元素是一个整数的首尾数字对。使用了二维数组dpdp[i][j]表示到下标i以数字j结尾的最长接龙序列的长度。
首先读取输入的序列长度n然后读取序列将每个元素的首尾数字对存入数组a。
接下来使用动态规划来计算最长接龙序列的长度。对于第i个元素遍历所有可能的末尾数字j。
状态转移方程如下
如果末尾数字 j 等于当前数字对 a[i] 的末尾数字那么状态 dp[i][j] 取 dp[i - 1][j] 和 dp[i - 1][a[i].first] 1 中的较大值。这表示如果可以在当前数字对 a[i] 的首位数字后接上 j那么就可以选择接上 j并使得接龙序列的长度增加 1否则就保持原来以 j 结尾的接龙序列不变。 d p [ i ] [ j ] max ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ a [ i ] . f i r s t ] 1 ) , if j a [ i ] . s e c o n d dp[i][j] \max(dp[i - 1][j], dp[i - 1][a[i].first] 1), \text{ if } j a[i].second dp[i][j]max(dp[i−1][j],dp[i−1][a[i].first]1), if ja[i].second
如果末尾数字 j 不等于当前数字对 a[i] 的末尾数字那么状态 dp[i][j] 等于 dp[i - 1][j]。这表示不能在当前数字对 a[i] 的首位数字后接上 j所以保持原来以 j 结尾的接龙序列不变。 d p [ i ] [ j ] d p [ i − 1 ] [ j ] , if j ≠ a [ i ] . s e c o n d dp[i][j] dp[i - 1][j], \text{ if } j \neq a[i].second dp[i][j]dp[i−1][j], if ja[i].second
最后遍历dp[n]找出最长的接龙序列长度m输出n - m即最少需要删除的数的个数。 AC代码
#include algorithm
#include iostream
#define mp make_pair
#define AUTHOR HEX9CF
using namespace std;
using ll long long;
using pii pairint, int;const int N 1e6 7;
const int INF 0x3f3f3f3f;
const ll MOD 1e9 7;int n;
pii a[N];
// 到下标i以j结尾的最长接龙序列
ll dp[N][15];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;for (int i 1; i n; i) {string s;cin s;a[i] {*s.begin() - 0, *s.rbegin() - 0};}for (int i 1; i n; i) {for (int j 0; j 9; j) {if (j a[i].second) {dp[i][j] max(dp[i - 1][j], dp[i - 1][a[i].first] 1);} else {dp[i][j] dp[i - 1][j];}}}ll m 0;for (int j 0; j 9; j) {m max(m, dp[n][j]);}cout n - m \n;return 0;
}
