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