该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T4. 字符串转换

题目描述

小蓝正在学习文本编辑，她有两个字符串 $A$ 和 $B$。她希望通过若干次操作将字符串 $A$ 变成字符串 $B$。允许的操作有三种：

1. 删除：删除 $A$ 中的一个字符，代价为 $c_d$。
2. 插入：在 $A$ 的任意位置插入一个字符，代价为 $c_i$。
3. 替换：将 $A$ 中的一个字符替换为另一个字符，代价为 $c_r$。

注意：操作的代价是正整数，且三种操作的代价可能各不相同。

请你帮助小蓝计算：将字符串 $A$ 变为字符串 $B$ 所需的最小总代价。

输入格式

第一行一个字符串 $A$。

第二行一个字符串 $B$。

第三行三个整数 $c_d, c_i, c_r$，分别表示删除、插入、替换操作的代价。

输出格式

输出一行一个整数，表示最小总代价。

样例

样例 #1

输入样例(t4.in)

abc
abd
2 3 1

输出样例(t4.out)

1

解释：将 c 替换为 d，代价 $c_r = 1$，总代价 $1$。也可以先删除 c（代价 $2$）再插入 d（代价 $3$），总代价 $5$。最小为 $1$。

样例 #2

输入样例

horse
ros
1 1 1

输出样例

3

解释：经典编辑距离，删除、插入、替换代价均为 $1$。最少需要 $3$ 步： horse → 替换 h 为 r → rorse → 删除第 $3$ 个 r → rose → 删除 e → ros。

样例 #3

输入样例

ab
ba
1 2 3

输出样例

3

解释：删除代价 $1$，插入代价 $2$，替换代价 $3$。

方案一：先删除 a（代价 $1$）得到 "b"，再在末尾插入 a（代价 $2$）得到 "ba"，总代价 $3$。

方案二：先删除 b（代价 $1$）得到 "a"，再在前面插入 b（代价 $2$）得到 "ba"，总代价 $3$。

方案三：两次替换（代价 $3+3=6$）。最小为 $3$。

数据范围与提示

对于 $100\%$ 的数据，$1 \le |A|, |B| \le 1000$，$1 \le c_d, c_i, c_r \le 1000$。字符串 $A, B$ 仅由小写英文字母组成。

提示：

• 定义 $dp[i][j]$ 表示将 $A$ 的前 $i$ 个字符转换为 $B$ 的前 $j$ 个字符所需的最小代价（$0 \le i \le |A|$，$0 \le j \le |B|$）。
• 初始化：
  • $dp[0][0] = 0$；
  • $dp[i][0] = i \times c_d$（删除 $A$ 的前 $i$ 个字符）；
  • $dp[0][j] = j \times c_i$（插入 $B$ 的前 $j$ 个字符）。
• 转移方程（$1 \le i \le |A|$，$1 \le j \le |B|$）：
  • 删除：$dp[i-1][j] + c_d$
  • 插入：$dp[i][j-1] + c_i$
  • 替换/匹配：$dp[i-1][j-1] + (A[i-1] == B[j-1] \;?\; 0 : c_r)$
  • $dp[i][j] = \min(删除, 插入, 替换/匹配)$
• 字符串下标从 $0$ 开始，注意与 DP 状态下标（从 $1$ 开始）的对应关系。
• 时间复杂度 $O(|A| \times |B|)$，空间可优化为 $O(|B|)$（滚动数组）。