【美团笔试】题解
前面的代码太简单了，就不贴了
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;
}