接龙序列（14届）-Toy模板网

这篇具有很好参考价值的文章主要介绍了接龙序列（14届）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

例如 12,23,35,56,61,11 是接龙数列；12,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

输出样例：

样例解释

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

接龙序列（14届）,蓝桥杯,蓝桥杯,dp

文章来源地址https://www.toymoban.com/news/detail-637613.html

#include<iostream>
using namespace std;
const int N=1e5+10;
int f[N];//以i结尾的最长接龙序列（跟最长上升子序列一个思路）
int l[N],r[N];//l[N]存储一个数的首位数字 r[N]存储一个数字的末位数字
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        string s;cin>>s;
        l[i]=s[0]-'0';
        r[i]=s[s.size()-1]-'0';
    }
    int res=0;
    //(最长上升子序列的思路 但是N=1e5 会超时)
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
        {
            if(r[j]==l[i]) f[i]=max(f[i],f[j]+1);
        }
        res=max(f[i],res);
    }
    cout<<n-res<<endl;
    return 0;
}

优化版

#include<iostream>
using namespace std;
const int N=1e5+10;
int f[N];//以i结尾的最长接龙序列（跟最长上升子序列一个思路）
int l[N],r[N];//l[N]存储一个数的首位数字 r[N]存储一个数字的末位数字
int g[10];//用来存储第i数字之前 以末尾数字k(0<=k<=9)为结尾的接龙序列的max
          //即g[k]表示在第i个数字以前,为k为末尾的接龙序列的最大长度
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        string s;cin>>s;
        l[i]=s[0]-'0';
        r[i]=s[s.size()-1]-'0';
    }
    int res=0;
    //(最长上升子序列的思路 但是N=1e5 会超时)
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        //由于第i个数字的首位为l[i],那么只关心前i个数字之前以l[i]结尾的最长接龙序序列就好
        f[i]=max(f[i],g[l[i]]+1);
        //更新 由于第i个数字的末尾为r[i],那么就要更新g[r[i]]
        g[r[i]]=max(f[i],g[r[i]]);
        res=max(f[i],res);
    }
    cout<<n-res<<endl;
    return 0;
}

到了这里，关于接龙序列（14届）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！