P9242 [蓝桥杯 2023 省 B] 接龙数列

这道题说要求最少删多少个使剩下的序列是接龙序列，这个问题可以转换为序列中最长的接龙序列是多少，然后用总长度减去最长接龙序列的长度就可以了，在第一个暴力版本的代码中我用了两个for循环求出了所有的接龙序列的长度，但是会超时，这道题可以用动态规划思想，动态规划思路是将问题转换为求序列中最长接龙序列长度，用序列总长度减去该长度得到最少删除数字个数；使用 map<char, int> mapp 记录以每个数字最后一个字符结尾的最长接龙序列长度，遍历序列中每个数字 

• 对于每个数字 s[j]，考虑其是否能接入到以 s[j] 的第一个字符结尾的接龙序列中。状态转移方程为 mapp[s[j][k - 1]] = max(mapp[s[j][k - 1]], mapp[s[j][0]] + 1)。
• max(mapp[s[j][k - 1]], mapp[s[j][0]] + 1) 的含义是：如果选择把 s[j] 接入到以 s[j] 的第一个字符结尾的接龙序列中，那么以 s[j] 的最后一个字符结尾的最长接龙序列长度就是以 s[j] 的第一个字符结尾的最长接龙序列长度加 1；若不选择接入，mapp[s[j][k - 1]] 的值保持不变，即维持其原本记录的最长接龙序列长度。

遍历完后找出 mapp 中最大值即最长接龙序列长度。

 

对于一个长度为 K 的整数数列：A1​,A2​,…,AK​，我们称之为接龙数列当且仅当 Ai​ 的首位数字恰好等于 Ai−1​ 的末位数字（2≤i≤K）。

例如 12,23,35,56,61,11 是接龙数列；12,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。

现在给定一个长度为 N 的数列 A1​,A2​,…,AN​，请你计算最少从中删除多少 个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1​,A2​,…,AN​。

输出格式

一个整数代表答案。

输入输出样例

输入 #1复制

5
11 121 22 12 2023

输出 #1复制

1

说明/提示

【样例说明】

删除 22，剩余 11,121,12,2023 是接龙数列。

【评测用例规模与约定】

对于 20% 的数据，1≤N≤20。

对于 50% 的数据，1≤N≤104。

对于 100% 的数据，1≤N≤105，1≤Ai​≤109。所有 Ai​ 保证不包含前导 0。

蓝桥杯 2023 省赛 B 组 E 题。

暴力版代码，会超时只能过三个样例

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
map<string,int>mapp;
string s[N];
signed main()
{int n;cin>>n;if(n==1){cout<<0;exit(0);}for(int i=1;i<=n;i++){cin>>s[i];mapp[s[i]]=1;}int sum=-1;for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){int k=s[i].size();// cout<<s[i]<<" "<<s[j]<<" "<<s[i][k-1]<<" "<<s[j][0]<<endl; if(s[i][k-1]==s[j][0]){mapp[s[j]]=max(mapp[s[j]],mapp[s[i]]+1);sum=max(sum,mapp[s[j]]);}}}cout<<n-sum;// 请在此输入您的代码return 0;
}

AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
map<char,int>mapp;
string s[N];
signed main()
{int n;cin>>n;if(n==1){cout<<0;exit(0);}for(int i=1;i<=n;i++){cin>>s[i];int k=s[i].size();mapp[s[i][k-1]]=0;}int sum=-1;for(int j=1;j<=n;j++){int k=s[j].size();mapp[s[j][k-1]]=max(mapp[s[j][k-1]],mapp[s[j][0]]+1);sum=max(sum,mapp[s[j][k-1]]);// cout<<sum<<" ";}cout<<n-sum;// 请在此输入您的代码return 0;
}