← 返回题单

题单练习双序列型DP入门

← 上一题下一题 →

A6972 | $编辑距离(pro 版本)$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有两个字符串 $A, B$，每次可以对 $A$ 进行 $4$ 种操作： 1. 插入一个字符，花费 $t_i$ 元； 2. 删除一个字符，花费 $t_d$ 元； 3. 替换一个字符，花费 $t_r$ 元； 4. 交换相邻的两个字符，花费 $t_e$ 元。 保证费用都是 $[1, 100]$ 之间的正整数，且 $2t_e\geq t_i + t_d$。 求将 $A$ 变成 $B$ 最少需要多少元。

输入格式

第一行四个整数 $t_i, t_d, t_r, t_e$。 接下来两行，每行一个字符串分别表示 $A, B$，保证它们长度都不超过 $4000$。

输出格式

一行一个整数表示最小费用。

输入输出样例

输入 #1

1 1 1 1
youshouldnot
thoushaltnot

输出 #1

输入 #2

2 4 10 3
ab
ba

输出 #2

输入 #3

1 10 20 30
a
za

输出 #3

C++ 编辑器

输入

输出