思路:
做题要想到用对立面解题,要求最短的,就可以先求最长的
//先求最长的接龙序列的长度maxx,再用长度n减去maxx
//先声明dp数组,记录以0-9结尾的最长的接龙数列的长度
//以字符串的形式输入
//更新以b结尾的最大接龙序列长度,当前数字是以b结尾,dp【a】是只以开头数字结尾的最大接龙序列的长度,+1是加上当前这个数字
//在更新最大的长度 maxx
//要删除的就是原先的数字长度-最长的接龙长度
代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int dp[10];//记录以0-9结尾的最长的接龙数列的长度
int main()
{
int n;
scanf("%d",&n);
int maxx = 0;
for(int i=0;i<n;i++)//以字符串的形式输入
{
char str[10000];
cin >> str;
int len = strlen(str);
int a = str[0] - '0';//第一个数字
int b = str[len-1] - '0';//最后一个数字
dp[b] = max(dp[b],dp[a]+1);//更新以b结尾的最大接龙序列长度,当前数字是以b结尾,dp【a】是只以开头数字结尾的最大接龙序列的长度,+1是加上当前这个数字
maxx = max(maxx,dp[b]); //在更新最大的长度
}
cout<<n-maxx<<endl;//要删除的就是原先的数字长度-最长的接龙长度
return 0;
}