蓝桥杯2023年-接龙数列（dp）

题目描述

对于一个长度为 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，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

思路

能想到dp就基本上知道咋写了。

dp[i]表示以选第i个数，所能够构成的最长序列。st表示第i个数的开头的数字，ed表示第i个数的结尾的数字。

则dp[i]=max{dp[前面以st结尾的数字]}。

优化：可以记录每个字母的最大结尾的长度，每次更新只需要考虑ed即可。

代码

#include<bits/stdc++.h>
using namespace std;

int dp[100005];
vector<string>str;
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        string s;cin>>s;
        str.push_back(s);
    }
    dp[0]=1;
    int mx[10]={0};
    int ans=0;
    for(int i=0;i<n;i++){
        int st=str[i].front()-'0';
        int ed=str[i].back()-'0';
        dp[i]=mx[st]+1;
        if(dp[i]>mx[ed]){
            mx[ed]=dp[i];
        }
        ans=max(ans,dp[i]);
    }
    cout<<n-ans;
    
}