第十四届省赛大学B组(C/C++)接龙数列

简介: 第十四届省赛大学B组(C/C++)接龙数列

题目链接:接龙数列

对于一个长度为 K 的整数数列:A1,A2,...,AK我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2≤i≤K)。

例如 12,23,35,56,61,1112,23,35,56,61,11 是接龙数列;12,23,34,5612,23,34,56 不是接龙数列,因为 56 的首位数字不等于 34 的末位数字。


所有长度为 1 的整数数列都是接龙数列。


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


输入格式


第一行包含一个整数 N。


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


输出格式


一个整数代表答案。


数据范围


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

对于 50%50% 的数据,1≤N≤10000。

对于 100%100% 的数据,1≤N≤10^5,1≤Ai≤10^9。所有 Ai 保证不包含前导 0。


输入样例:

5
11 121 22 12 2023

输出样例:

1

样例解释

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


解题思路:

此题的正解是动态规划,开始想到的是爆搜,dfs直接全部遍历寻找最大的接龙序列,dfs的话时间复杂度最好也就O(n^2),肯定过不了,正解为动态规划,dp[i][j]表示前i个数中,以j结尾最长接龙序列的长度,面对第i个数(头为a尾为b)满足条件可选可不选,选:dp[i][b]=dp[i-1][a]+1,不选:dp[i][b]=dp[i-1][b],dp[i][b]=max(dp[i-1][a]+1,dp[i-1][b]),那么这样便可以解决此题,我们还可以优化掉第一维,直接以序列结尾为维度,因为给出的是顺序排好的,直接遍历一遍即可。

DFS爆搜版(WA):

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,res=0x3f3f3f;
int a[N];
bool vis[N];
int get_tail(int x){//获取尾部
  return x%10;
}
int get_head(int x){//获取头部
  while(x){
    if(x<10){
      break;
    }
    x/=10;
  }
  return x;
}
void dfs(int u,int last,int ans){//u表示此时第u个,last序列最后一个,ans删除的个数
  if(u==n&&ans<res){
    res=ans;
  }
  if(u>n){
    return;
  }
  if(get_head(a[u])==last){
    dfs(u+1,get_tail(a[u]),ans);
  }
    dfs(u+1,last,ans+1);
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  for(int i=1;i<=n;i++){
    dfs(i+1,get_tail(a[i]),i-1);
  }
  cout<<res<<endl;
  return 0;
}


DP版(正解):

#include <iostream>
using namespace std;
const int N=1e5+5;
int n,res;
int dp[10];
string s;
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>s;
    int a=s[0]-'0',b=s.back()-'0';//转化为数字
    dp[b]=max(dp[b],dp[a]+1);
    res=max(res,dp[b]);
  }
  cout<<n-res<<endl;
  return 0;
}


相关文章
|
7月前
|
机器学习/深度学习 算法 测试技术
【动态规划】C++算法:446等差数列划分 II - 子序列
【动态规划】C++算法:446等差数列划分 II - 子序列
|
6月前
|
算法 C++
【动态规划】斐波那契数列模型(C++)
【动态规划】斐波那契数列模型(C++)
|
7月前
|
C++
【PTA】​ L1-080 乘法口诀数列​(C++)
【PTA】​ L1-080 乘法口诀数列​(C++)
99 0
【PTA】​ L1-080 乘法口诀数列​(C++)
|
7月前
|
C++ Java 定位技术
C/C++每日一练(20230420) 存在重复元素II、外观数列、最优路线
C/C++每日一练(20230420) 存在重复元素II、外观数列、最优路线
118 0
C/C++每日一练(20230420) 存在重复元素II、外观数列、最优路线
|
7月前
|
索引 Python C++
C/C++每日一练(20230416) 数列第n项、整数转英文、数组最大值及索引
C/C++每日一练(20230416) 数列第n项、整数转英文、数组最大值及索引
60 0
C/C++每日一练(20230416) 数列第n项、整数转英文、数组最大值及索引
|
7月前
|
C++
『C/C++』Eg1:数列的前20项之和
『C/C++』Eg1:数列的前20项之和
|
C++
C/C++每日一练(20230505) 扩展兔子数列、删除重复项、寻找最小值
C/C++每日一练(20230505) 扩展兔子数列、删除重复项、寻找最小值
118 0
|
人工智能 C++
第十届蓝桥杯省赛 C++ B/C组 - 等差数列
第十届蓝桥杯省赛 C++ B/C组 - 等差数列
110 0
|
算法 C++
C/C++每日一练(20230510) 编辑距离、多数元素、数列累和
C/C++每日一练(20230510) 编辑距离、多数元素、数列累和
86 0
|
Unix C++
C/C++每日一练(20230507) 数列第n项值I/II、简化路径
C/C++每日一练(20230507) 数列第n项值I/II、简化路径
93 0