3152: 蓝桥杯2023年第十四届省赛真题-接龙数列

解题思路:

    动态规划

    用字符串来存，然后x是第一位，y是最后一位（比如22314  x=2  y=4）

    dp[y]表示以y数字为结尾的最长数列

    每次当前放或者不放取最优的状态，如果放，当前字符串的x就要和上一个的y一样，以y为结尾连下来的最优状态就是dp[y],加上当前的就是dp[x]+1

    状态转移方程：dp[y]=max(dp[y],dp[x]+1)

    

注意事项:

        一.没有前导零

        二.末尾可能为0

参考代码:

#include<iostream>

using namespace std;

int n;

const int N=1e5+10;

string s[N];

int dp[15];

int main(){

cin>>n;

for(int i=1;i<=n;i++) {

cin>>s[i];

int x=*s[i].begin()-'0';

int y=*(--s[i].end())-'0';

dp[y]=max(dp[y],dp[x]+1); 

}

int tt=0;

for(int i=0;i<10;i++) {

tt=max(tt,dp[i]);

}

cout<<n-tt;

return 0;

}