T1：Sequence Matching
本题难度中等，序列匹配问题，一般都可以考虑用类似公共子序列的DP方法。本题正是如此，考虑数组 \(a\) 的前缀和数组 \(b\) 的前缀匹配时，\(x+y\) 的最小值，推出状态转移即可
记 dp[i][j] 表示将 \(a_1 \sim a_i\) 与 \(b_1 \sim b_j\) 中删掉 \(x\) 个后不同位置个数为 \(y\)，\(x+y\) 的最小值
最后的答案为 \(dp[n][m]\)
状态转移：
- 删 \(a_i\)：\(a_1 \sim a_{i-1}\) 与 \(b_1 \sim b_j\) 匹配
\(dp[i-1][j]+1\) - 删 \(b_j\)：\(a_1 \sim a_i\) 与 \(b_1 \sim b_{j-1}\) 匹配
\(dp[i][j-1]+1\) - \(a_i = b_j\) 时都不删，\(a_1 \sim a_{i-1}\) 与 \(b_1 \sim b_{j-1}\) 匹配
然后在后面续上 \(a_i\) 和 \(b_j\)
\(dp[i-1][j-1]\) - \(a_i \neq b_j\) 也都不删
\(dp[i-1][j-1]+1\)
初值：
- \(dp[0][0] = 0\)
- \(dp[0][j] = j\)
- \(dp[i][0] = i\)
- 其他 \(dp = \infty\)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::min;
const int INF = 1001001001;
template<typename T>
void chmin(T& a, const T& b) { a = min(a, b); }
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
rep(i, n) cin >> a[i];
rep(i, m) cin >> b[i];
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));
dp[0][0] = 0;
rep(i, n + 1)rep(j, m + 1) {
if (i < n) chmin(dp[i + 1][j], dp[i][j] + 1);
if (j < m) chmin(dp[i][j + 1], dp[i][j] + 1);
if (i < n && j < m) {
int co = 0;
if (a[i] != b[j]) co = 1;
chmin(dp[i + 1][j + 1], dp[i][j] + co);
}
}
cout << dp[n][m] << '\n';
return 0;
}