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

解题思路:

状态转移方程看不懂，我也是不求甚解，先写下来

注意事项:

参考代码:

#include<iostream>

using namespace std;

const int N=15;

int dp[N];//定义dp，从0~9，只有10个数

int main()

{

    int a;//拿到用户输入的数据个数

    cin>>a;

    string b;//拿到用户每次输入的数，由于只看数字的开头和结尾，故用string更方便

    int ans=1e9;//设置无穷大

    for(int i=0;i<a;i++)

    {

        cin>>b;//拿到每次的数据

        dp[b.back()-'0']=max(dp[b.back()-'0'],dp[b.front()-'0']+1);//转移方程，求出最长数列

    }

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

    {

        ans=min(a-dp[i],ans);//用原本的数列减去最长数列就是最少删除数

    }

    cout<<ans;

    return 0;

}