P9242 [蓝桥杯 2023 省 B] 接龙数列

Convergent_Series · 2023-06-05 13:36:01 · 题解

计算去掉的数量不好思考，可以先算出最长的接龙数列长度，与 n 相减即为答案。

考虑使用动态规划计算。

令 dp_i 为以 i 结尾的最长序列，枚举到 a_i 时：

设 a_i 开头数字为 p，结尾数字为 q。

• 若选取 a_i，则 dp_q=dp_p+1;
• 若不选取 a_i，则 dp_q 不变。

所以可以得到状态转移方程为 dp_q=\max(dp_p+1,dp_q)。

最后答案即为 n-\max dp_i\ (0\le i\le9)。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,dp[10],maxn;
string a;//为了方便取头尾，可以以字符串形式存储
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        int ln=a.length();
        dp[a[ln-1]-'0']=max(dp[a[ln-1]-'0'],dp[a[0]-'0']+1);
    }
    for(int i=0;i<=9;i++) maxn=max(maxn,dp[i]);
    cout<<n-maxn;
    return 0;
}