DP ``` #include <iostream> #include <string> using namespace std; int dp[10]; int main(){ int n; cin >> n; string s; int m=0; for(int i=0;i<n;++i){ cin >> s; int x =s[0]-'0',y=s[s.size()-1]-'0'; dp[y]=max(dp[x]+1,dp[y]); m=max(m,dp[y]); } cout << n-m << endl; return 0; } ``` dp[y]=max(dp[x]+1,dp[y]); 用于更新以数字 y 结尾的最长序列的长度 假设我们有一系列字符串，每个字符串由两个数字组成，我们的目标是找到一个最长的字符串序列，使得每个字符串的第一个数字等于前一个字符串的最后一个数字。 例如，我们有以下字符串序列： ``` "11" "121" "22" "12" "2023" ``` 我们用 dp[i] 来表示以数字 i 结尾的最长序列的长度。初始时，所有的 dp[i] 都是0，因为我们还没有开始构建序列。 现在，我们开始处理每个字符串： 1. 对于字符串 “11”，x=1, y=1。因为这是第一个字符串，所以我们将 dp[1] 更新为 dp[1]+1，即 dp[1]=1。 2. 接下来是 “121”，x=1, y=1。我们查看 dp[1]，它是1，表示已经有一个长度为1的序列以1结尾。所以我们可以在这个序列后面加上 “121”，形成一个新的序列。因此，dp[1] 更新为 dp[1]+1，即 dp[1]=2。 3. 对于 “22”，x=2, y=2。查看 dp[2]，它是0，所以 dp[2] 更新为 dp[2]+1，即 dp[2]=1。 4. 对于 “12”，x=1, y=2。查看 dp[1]，它是2，所以 dp[2] 更新为 dp[1]+1，即 dp[2]=3。 5. 最后是 “2023”，x=2, y=3。查看 dp[2]，它是3。所以 dp[3] 更新为 dp[2]+1，即 dp[3]=4。 在这个过程中，m 用来记录我们找到的最长序列的长度。每次我们更新 dp[y] 时，我们都会检查它是否比 m 大。如果是，我们就更新 m。 最终，dp 数组和 m 的值如下： ``` dp[1] = 2, dp[2] = 3, dp[3] = 4, m = 4 ``` 这意味着我们可以构建一个长度为4的序列，所以 n-m 就是我们需要从原始序列中移除的字符串数量，以便剩下的字符串可以形成这样一个最长序列。在这个例子中，n=5 和 m=4，所以我们需要移除 5-4=1 个字符串。

见注释❤️ ```C++ #include <iostream> #include <string> #include <vector> using namespace std; int main() { // 最小删除多少个数 使得接龙数列 // 最小删除多少个数 == 原长 - 最长接龙数列 // 定义 dp[i][j] 是 i 开头 j 结尾的最长接龙序列长度 // 对于 a---b, b --- c 字符串 // 有 dp[a][c] = max( 自己, dp[a][b] + 1 ) // 现在 把目光放到 b---c 上, 则 a 实际上是未知(任意的), 故有如下代码 vector<vector<int>> dp(10, vector<int>(10, 0)); int n; cin >> n; int len = 0; for (int i = 0; i < n; ++i) { string s; cin >> s; for (int j = 0; j < 10; ++j) { dp[j][s[s.size() - 1] - '0'] = max(dp[j][s[s.size() - 1] - '0'], dp[j][s[0] - '0'] + 1); len = max(len, dp[j][s[s.size() - 1] - '0']); } } cout << n - len << "\n"; return 0; } ```

``` //最长上升子序列模型 #include<bits/stdc++.h> using namespace std; const int N = 100010; int l[N],r[N]; int f[N],g[10];//g为辅助数组,记录以x结尾的max int n; int main() { cin >> n; int res=0; char num[30]; for(int i=0;i<n;i++){ cin >> num; l[i]=num[0]-'0'; r[i]=num[strlen(num)-1]-'0'; } for(int i=0;i<n;i++){ f[i]=1; f[i]=max(f[i],g[l[i]]+1); g[r[i]]=max(g[r[i]],f[i]); // for(int j=0;j<i;j++){ // if(r[j]==l[i]) // f[i]=max(f[i],f[j]+1); // } res=max(res,f[i]); } cout<<n-res; return 0; } ``` ``` ```

``` #include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 10; int n; int dp[N]; signed main() { cin >> n; int ans = 0; for(int i = 1; i <= n; i ++ ) { string s; cin >> s; int a = s[0] - '0', b = s[s.size() - 1] - '0'; dp[b] = max(dp[b], dp[a] + 1); ans = max(ans, dp[b]); } cout << n - ans; } ```

不会dp,只能写个记忆化了（doge） ``` #include<bits/stdc++.h> using namespace std; int n,ans=1e8,dp[200][100005]; //对于当前这个下标，这条接龙的尾巴，你后面最长能接几个 int dfs(char ta,int k,int wo)//k表示长度 { if(wo==n+1) { return 0; } if(dp[ta][wo]!=-1)return dp[ta][wo]; if(a[wo].h==ta||ta==' ') dp[ta][wo]=dfs(a[wo].e,k+1,wo+1)+1;//可以不删 dp[ta][wo]=max(dp[ta][wo],dfs(ta,k,wo+1)); return dp[ta][wo]; } int main() { memset(dp, -1, sizeof(dp)); cin>>n; for(int i=1;i<=n;i++) { cin>>st; a[i].s=st; a[i].h=st[0]; a[i].e=st[st.size()-1]; } cout<<n-dfs(' ',0,1);; } ```

``` ``` import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 读取数列长度 int[] f = new int[10]; // 初始化数组f int ans = Integer.MAX_VALUE; // 初始化答案为最大整数值 // 遍历输入的每个数字字符串 for (int i = 1; i <= n; i++) { String s = scanner.next(); int lastDigit = s.charAt(s.length() - 1) - '0'; // 获取字符串的最后一个字符的数字 int firstDigit = s.charAt(0) - '0'; // 获取字符串的第一个字符的数字 // 更新数组f f[lastDigit] = Math.max(f[lastDigit], f[firstDigit] + 1); } // 找出最小的f值，即最长的接龙数列 for (int i = 0; i < 10; i++) { ans = Math.min(ans, n - f[i]); } System.out.println(ans); // 输出答案 scanner.close(); // 关闭scanner } } ``` ```

``` n = int(input()) ls = [0]+list(input().split()) dp = [[0]*15 for i in range(n+5)] for i in range(1,n+1): for j in range(10): dp[i][j] = dp[i-1][j]+1 final = int(ls[i][-1]) first = int(ls[i][0]) dp[i][final] = min(dp[i-1][first],dp[i][final]) ans = float('inf') for i in range(10): ans = min(ans,dp[n][i]) print(ans) ```

include using namespace std; int head[100000], rear[100000], res[100000], tmp[100000]; int main() { int n, result = 0; char input[1000000]; scanf("%d", &n); for (int i = 0; i > input; // 以空格符(回车，空格)结束 head[i] = input[0] - int('0'); rear[i] = input[strlen(input) - 1] - int('0'); } for (int i = 0; i < n; i++) { res[i] = 1; res[i] = max(res[i], tmp[head[i]] + 1); tmp[rear[i]] = max(tmp[rear[i]], res[i]); result = max(res[i], result); } cout << (n - result); return 0; }

动态规划 ``` #include<bits/stdc++.h> #include<vector> using namespace std; const int MAX_N = 1e5 +5; int N, dp[10]; int main() { ios::sync_with_stdio(0);cin.tie(0); cin>>N; for(int i = 1;i <= N;++i) { int A; cin >> A; vector<int>d; while(A) { d.push_back(A % 10); A /= 10; } int y = *d.begin(), x = d.back(); dp[y] = max(dp[y], dp[x] + 1); } int len = 0; for(int i = 0;i < 10;i++) { len = max(len,dp[i]); } cout<<N - len<<endl; return 0; } ```

接龙序列 Problem 对于一个长度为 $K$ 的整数数列：$A_1,A_2,...,A_K$，我们称之为接龙数列当且仅当 $A_i$ 的首位数字恰好等于 $A_{i−1}$ 的末位数字 $(2≤i≤K)$。 例如 $12,23,35,56,61,11$ 是接龙数列；$12,23,34,56$ 不是接龙数列，因为 $56$ 的首位数字不等于 $34$ 的末位数字。 所有长度为 $1$ 的整数数列都是接龙数列。 现在给定一个长度为 $N$ 的数列 $A_1,A_2,...,A_N$，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？ 输入格式 第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $A_1,A_2,...,A_N$。 输出格式 一个整数代表答案。 数据范围 对于 $20\%$ 的数据，$1≤N≤20$。 对于 $50\%$ 的数据，$1≤N≤10000$。 对于 $100\%$ 的数据，$1≤N≤10^5$，$1≤A_i≤10^9$。所有 $A_i$ 保证不包含前导 $0$。 输入样例： ``` 5 11 121 22 12 2023 ``` 输出样例： ``` 1 ``` 样例解释 删除 $22$，剩余 $11,121,12,2023$ 是接龙数列。 Solutions 题目转换： + 题目描述说“请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？”，“最少删除”即为求最长的接龙序列。 + 朴素版就是借鉴 $LIS$ 朴素版的做法。 + 优化版是每次找第 $i$ 个数之前的数，其实只需要用到尾字母 $r$，所以只需要开一个数组f[N],其中f[i]表示尾字母是 $i$ 的数的接龙序列的最大长度。（具体看代码，代码非常优美） AC Code 朴素版 $O(n^2)$ $TLE$ ```cpp #include <bits/stdc++.h> using namespace std; const int N=1e5+10; int f[N],h[N],r[N]; int main() { int n; cin>>n; for(int i=0;i<n;++i) { string str; cin>>str; h[i]=str.front()-'0',r[i]=str.back()-'0';//记录第i个数的首字母和尾字母 } for(int i=0;i<n;++i) f[i]=1; for(int i=0;i<n;++i) { for(int j=0;j<i;++j) { //找第i个数之前的尾字母数是h的数,可以借到它的后面 if(r[j]==h[i]) f[i]=max(f[i],f[j]+1); } } int res=0; for(int i=0;i<n;++i) res=max(res,f[i]); cout<<n-res<<endl; return 0; } ``` 优化版 $O(n\log{n})$ ```cpp #include <bits/stdc++.h> using namespace std; const int N=100; int f[N];//f[i]表示当前以数字i结尾的最长序列长度 int main() { int n; cin>>n; int maxLen=0;//最长接龙序列长度 for(int i=0;i<n;++i) { string str; cin>>str; int h=str.front()-'0';//首字母 int r=str.back()-'0';//尾字母 f[r]=max(f[r],f[h]+1);//当前这数字的应该接到尾字母是h的数字后面 //特殊情况,如果找不到尾字母是h的数,那么f[r]=1(f[r]=f[h]+1,此时f[h]==0) //f[r]更新用max去更新,不要写成f[r]=f[h]+1 maxLen=max(maxLen,f[r]); } cout<<n-maxLen<<endl; return 0; } ``` Note 状态表示：f[i]表示以数字i结尾的接龙序列的最长长度 状态转移：f[r]=max(f[r],f[h]+1)，其中h为str_num的首字母，r为str_num的尾字母 + 比如字符串23，f[3]有两个选择 + f[3]=f[2]+1：23接到xx2的后面 + f[3]=f[3]：f[3]可以由其他字符串表示，以数字3结尾的接龙序列的最后一个字符串不一定是23，也可以是其他的字符串