首页 > 编程语言 >第十四届省赛大学B组(C/C++)接龙数列

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

时间:2024-03-31 17:33:24浏览次数:42  
标签:数列 23 int get C++ 接龙 省赛 dp

题目链接:接龙数列

对于一个长度为 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;
}

标签:数列,23,int,get,C++,接龙,省赛,dp
From: https://blog.csdn.net/m0_73633807/article/details/137202958

相关文章

  • 【每周例题】力扣 C++ 二叉树的最小深度
    二叉树的最小深度题目二叉树的最小深度题目分析1.首先我们可以处理最小深度为0与最小深度为1的情况:最小深度为0:头结点为空;root==nullptr最小深度为1:root->left==nullptr&&root->right==nullptr2.接下来分为左右子树处理,我们可以用递归来计算最小深度3.最后比较左......
  • 【每周例题】力扣 C++ 搜索插入位置
    搜索插入位置题目搜索插入位置 题目分析1.第一个想法肯定是暴力遍历,找到了就输出下标,找不到就对比前后两个数字,寻找合适的位置插入。2.需要注意一点,我们需要再一开始就对比target与数组最后一个数的大小,如果比数组最后一个数大,直接返回数组长度3.第二个想法就是缩短寻找的......
  • [C++11]右值引用
    阅读导览:通过左值、右值的基础概念来引出左值引用和右值引用知道左值引用和右值引用后,先了解他们为什么能实现(底层原理)熟悉了解左值引用的优点和缺陷并给出疑问,进而引出右值引用出现的意义以及如何解决左值引用的疑问最后从多个方面再次了解右值引用基础概念右值、左值......
  • C++类(class)中的this指针与静态成员
    1.this指针作用:指向成员函数所作用的对象2.静态成员定义方式:在定义成员时加static关键字。访问方式:不用通过对象就可以访问(类似全局变量/全局函数)目的:设置静态成员这种机制的目的是将和某些类紧密相关的全局变量和函数写到类里面,看上去像一个整体,易于维护和理解。①......
  • 蓝桥杯2015年第十三届省赛真题-三羊献瑞
    一、题目观察下面的加法算式:   祥瑞生辉 + 三羊献瑞---------------------- 三羊生瑞气(如果有对齐问题,可以参看【图1】)其中,相同的汉字代表相同的数字,不同的汉字代表不同的数字。请你填写“三羊献瑞”所代表的4位数字(答案唯一),不要填写任何多余内......
  • 蓝桥杯2018年第十三届省赛真题-复数幂
    一、题目复数幂设i为虚数单位。对于任意正整数n,(2+3i)^n的实部和虚部都是整数。求(2+3i)^123456等于多少?即(2+3i)的123456次幂,这个数字很大,要求精确表示。答案写成"实部±虚部i"的形式,实部和虚部都是整数(不能用科学计数法表示),中间任何地方都不加空格,实部为正时前面......
  • 蓝桥杯2016年第十三届省赛真题-生日蜡烛
    一、题目生日蜡烛.某君从某年开始每年都举办一次生日party,并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来,他一共吹熄了236根蜡烛。请问,他从多少岁开始过生日party的?请填写他开始过生日party的年龄数。注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字......
  • 蓝桥杯2021年第十三届省赛真题-直线
    一、题目【问题描述】    在平面直角坐标系中,两点可以确定一条直线。如果有多点在一条直线上,那么这些点中任意两点确定的直线是同一条。    给定平面上2×3个整点{(x,y)|0≤x<2,0≤y<3,x∈Z,y∈Z},即横坐标是0到1(包含0和1)之......
  • 蓝桥杯2014年第十三届省赛真题-猜字母
    一、题目猜字母  把abcd...s共19个字母组成的序列重复拼接106次,得到长度为2014的串。  接下来删除第1个字母(即开头的字母a),以及第3个,第5个等所有奇数位置的字母。  得到的新串再进行删除奇数位置字母的动作。如此下去,最后只剩下一个字母,请写出该字母。答案是......
  • 蓝桥杯2020年第十三届省赛真题-合并检查
    一、题目合并检测新冠疫情由新冠病毒引起,最近在A国蔓延,为了尽快控制疫情,A国准备给大量民众进病毒核酸检测。然而,用于检测的试剂盒紧缺。为了解决这一困难,科学家想了一个办法:合并检测。即将从多个人(k个)采集的标本放到同一个试剂盒中进行检测。如果结果为阴性,则说明这k......