当前位置: 首页> 娱乐> 明星 > 大连app开发公司排名_徐州代办公司_天津网站建设技术外包_友情链接平台哪个好

大连app开发公司排名_徐州代办公司_天津网站建设技术外包_友情链接平台哪个好

时间:2025/7/10 18:03:43来源:https://blog.csdn.net/2403_86696801/article/details/146996986 浏览次数:1次
大连app开发公司排名_徐州代办公司_天津网站建设技术外包_友情链接平台哪个好

题目描述

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

//深度优先搜索代码
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef struct {
    int first;
    int last;
}num;
//记录最高位 最低位

vector<num> A;
//存储第i个数字最高位 最低位

int N;
//原序列的长度

int max_lend=1;
//接龙序列的最长度

vector<int> niha;
num getNum(int data){
    int first,last=data%10; 
    int temp=data;
    while(data){
        first=data%10;
        data/=10;
    }
    return {first,last};
}

//正在处于第index个数字  当前的接龙序列长度 当前接龙序列最后一位是last_digit 
void dfs(int index,int curr_lend,int last_digit){
    if(index==N){
        max_lend=max(max_lend,curr_lend);
        return;
    }

//剪枝操作

    if(N-index-1+curr_lend<max_lend)return;
    //选择
    if(curr_lend==0||A[index].first==last_digit) 
    dfs(index+1,curr_lend+1,A[index].last);
    //不选择 
    dfs(index+1,curr_lend,last_digit);
}
int main(){
    cin>>N;
    for(int i=0;i<N;i++){
        int temp;
        cin>>temp;
        A.push_back(getNum(temp));
    }    
    dfs(0,0,-1);

    cout<<N-max_lend<<endl;

    return 0;
}

//动态规划代码


 

关键字:大连app开发公司排名_徐州代办公司_天津网站建设技术外包_友情链接平台哪个好

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: