[ABC185E] Sequence Matching
1 Solution
令 f
i,j
表示 A 序列前 i − 1 个字符，B 序列前 j − 1 个字符的最小权值。那么，转移分为三种情况：
不选 A
i
: f
i+1,j
← f
i,j
+ 1
不选 B
j
: f
i,j+1
← f
i,j
+ 1
选 A
i
和 B
j
: f
i+1,j+1
← f
i,j
+ (A
i
= B
j
)，如图1。
下面来写一下行内公式：x
2
− y
2
= (x − y)(x + y)。
再试一下行间公式：
(x
2
− y
2
) × (x + y) = (x − y)(x + y)(x + y)
= (x − y)(x + y)
2
Figure 1: C
3
+ C
5
2 Code
2.1 hitonanode 的代码
hitonanode 的代码 1 。
Algorithm 1 hitonanode 的代码
int main()
{
int N, M;
cin >> N >> M;
vector<int> A(N), B(M);
cin >> A >> B;
vector dp(N + 2, vector<int>(M + 2, 1 << 30));
dp[0][0] = 0;
REP(i, N + 1) REP(j, M + 1) {
chmin(dp[i][j + 1], dp[i][j] + 1);
chmin(dp[i + 1][j], dp[i][j] + 1);
1
