[蓝桥杯2023年第十四届省赛真题-接龙数列] 类最长上升子序列dp做法

解题思路: 可以先求最长可以组成的序列，相减就是最少删除了。


参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct T {

    int l, r;

}w[N];

int dp[N], g[10];

int main(void) {

    int n;

    cin >> n;

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

        string s;

        cin >> s;

        w[i] = {s[0] - '0', s.back() - '0'};

    }    

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

        dp[j] = 1;

        dp[j] = max(dp[j], g[w[j].l] + 1);

        g[w[j].r] = max(dp[j], g[w[j].r]);

    }

    int ans = -1;

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

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

    }

    printf("%d\n", n - ans);

    return 0;

}