Oiclass P1242 题解

这道题真的离谱

1. 划分阶段

对于这道题目，我以每一个字母为一个阶段，表示第一个字符串的前 \(i\) 个字母和第二个字符串的前 \(j\) 个字母之间的编辑距离（定义见题目）

2. 状态和状态变量

定义数组 \(f\) 用于存储状态，即 \(f_{i,\ j}\) 表示一个阶段（也就是(1) 里面提到的阶段），同时 \(a,b\) 分别是输入的两个字符串

3. 确定状态转移方程

这就是最难的部分，先从 \(f_{i,\ j}\) 的三种可能性看起，他们可能有以下三种状态： \[ \left\{ \begin{array}{lr} a_i="\ "\\ b_j="\ "\\ a_i≠"\ "\ \&\&\ b_j≠"\ " \end{array} \right. \]

那么先从第一种，也就是当 \(a_i\) 是空格，而 \(b_j\) 不是的时候，在这个时候，状态转移方程应该如下： \[ f_{i,\ j} = f_{i - 1,\ j} + k\ \ （k\ 与题目中的定义相同） \]

然后是第二种，也就是 \(b_j\) 是空格，但是 \(a_i\) 不是空格的时候，方程如下： \[ f_{i,\ j} = f_{i,\ j-1} + k\ \ \ （k\ 的定义与题目中相同） \] 然后是最后一种，实际上也是最简单的一种： \[ f_{i,\ j} = f_{i - 1,\ j- 1} + |a_i-b_j| \] 行，这就是所有的状态转移方程，总结一下，如下： \[ f_{i,\ j} = \left\{ \begin{array}{lr} a_i ="\ "\ \ \ f_{i - 1,\ j} + k\\ b_j="\ " \ \ \ f_{i,\ j - 1} + k\\ a_i≠"\ "\ \&\&\ b_j≠"\ "\ \ \ \ f_{i-1,\ j-1} + |a_i - b_j| \end{array} \right. \]

4. 边界条件

观察样例可以发现，边界条件就是这样的： \[ \begin{array}{lr} f_{i,\ 0} = f_{i-1,\ 0} + k\\ f_{0,\ j} = f_{0,\ j-1} + k\\ \end{array} \]

5. 实现

终于到了最最最最最最简单的一步：实现（手动洒花

实现真的很简单，只需要以下几步：

• 输入
• 给边界条件赋值
• 计算，也就是取 \(f_{i,\ j}\) 三种可能性之中值最小的一种给 \(f_{i,\ j}\) 赋值
• 输出，把 \(f_{a.length(),\ b.length()}\) 输出
• 等 AC

下面是实际代码：

#include<iostream>

using namespace std;
int k, f[2009][2009];
string a, b;

int main() {
    cin >> a >> b >> k;
    for (int i = 1; i <= a.length(); i++) {
        f[i][0] = k + f[i - 1][0];
    }
    for (int i = 1; i <= b.length(); i++) {
        f[0][i] = k + f[0][i - 1];
    }
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            f[i][j] = min(f[i - 1][j - 1] + abs((int) a[i - 1] - (int) b[j - 1]), min(f[i - 1][j] + k, f[i][j - 1] + k));
        }
    }
    cout << f[a.length()][b.length()];
}