套10 A 编辑距离
题目描述
给定两个由小写字母组成的字符串 s, t ，你可以对 s 进行以下四种操作：
1.在任意位置添加任意一个字母，代价为 a 。
2.删除任意一个字母，代价为 b 。
3.替换任意一个字母，代价为 c 。
4.交换相邻两个字母，代价为 d 。你需要求出将 s 变为 t 的最小代价。
部分分
刚看到这道题不是很有头绪，尝试用DP乱搞一下
我们用 f_{i,j} 表示将 s 的前 i 位变为 t 的前 j 位所需的最小代价，接下来就是考虑DP方程怎么写了
对于操作1，如果 s 的前 i 位已经能够变成 t 的前 j-1 位，那么我们只需要进行 1 次操作1 添加 t 的第 j 位字母即可将 s 的前 i 位变为 t 的前 j 位，花费代价为 a
对于操作2，如果 s 的前 i-1 位已经能够变成 t 的前 j 位，那么我们只需要进行 1 次操作2 删除 s 的第 i 位字母即可将 s 的前 i 位变为 t 的前 j 位，花费代价为 b
对于操作3，如果 s 的前 i-1 位已经能够变成 t 的前 j-1 位，那么我们只需要进行 1 次操作3 将 s 的第 i 位字母替换为 t 的第 j 位字母即可将 s 的前 i 位变为 t 的前 j 位，花费代价为 c
到这里，因为题目中对于另外 30% 的数据，保证存在一种最优解不使用操作4。所以已经30分到手了，况且操作4太麻烦不想做
正解
就是多考虑一个操作4的事
注意到数据保证：2d≥a+b ，它很厉害，这说明对于同一字母，我们绝不会对其执行两遍操作4，例如对于 abc 中，我们将 a 删去并在 c 后加上 a 得到 bca 与直接将 a 与后一位连续进行2次操作4得到 bca 相比，前者代价 a+b 是被保证优于后者代价 2d 的
因此我们对于一个字母只需要考虑一次操作4
对于操作4，我们在 s 中找到最后一次出现与 t 的第 j 位相同字母的位置，记为 k ,在 t 中找到最后一次出现与 s 的第 i 位相同字母的位置，记为 l ，然后进行下图操作
花费代价为： (i-k-1)*b+(j-l-1)*a+d
方程出来后，代码实现很好写，就不展示了