【美团笔试】题解
前面的代码太简单了,就不贴了
T5
考虑原序列前缀与变化后序列后缀的最长匹配长度,dp预处理子串的匹配长度。
应该直接枚举长度,然后比较两个字符串前后缀是否相等也行
#include <bits/stdc++.h> using namespace std; void solve(){ int n, m; cin >> n; vector <int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; cin >> m; vector <int> b(m); for(int i = 0; i < m; i++) cin >> b[i]; vector <vector<int>> f(n + 1, vector <int> (m + 1)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(a[i - 1] == b[j - 1]){ f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1); } } } int t = 0; for(int i = 1; i <= n; i++){ if(f[i][m] == i) t = max(t, f[i][m]); } cout << n + m - 2 * t << endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; t = 1; while(t--){ solve(); } return 0; }