蓝桥杯day21刷题日记--接龙序列 动态规划

刚开始以为最长子序列的做法，然后发现数据太大了，只能得四十分，遂看题解，寻找AC做法

四十分做法

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[100010];
int n;
string s;
int head[100010],tail[100010];
 
int main()
{
    cin>>n;
    int maxs=1; 
    for(int i=1;i<=n;i++){
        cin>>s;
        head[i]=s[0]-'0';
        tail[i]=s[s.size()-1]-'0';
    }
    dp[1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++)
            if(head[i]==tail[j])
                dp[i]=max(dp[i],dp[j]+1);
        maxs=max(maxs,dp[i]);    
    }
    cout<<n-maxs;
    return 0;
}

AC做法 

核心就是一个数能否接龙是由它的自身第一个数字决定的，所以用dp[i]代表以i为结尾的数的最长接龙长度

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[20];
int n;
string s;
 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        dp[s.back()-'0']=max(dp[s.back()-'0'],dp[s.front()-'0']+1);
    }
    int maxs=-1e9;
    for(int i=0;i<10;i++) maxs=max(maxs,dp[i]);
    cout<<n-maxs;
    return 0;
}