思路:
做题要想到用对立面解题,要求最短的,就可以先求最长的
//先求最长的接龙序列的长度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;
}