字串距离

Posted by Panda2134's Blog on July 24, 2017

链接:Luogu-1279

思路

如何实现“插入空格”操作?

定义状态为$f(i,j)$,表示字符串A中从第$i$个字符到结尾,字符串B中从第$j$个字符到结尾,所能得到的最小字串距离。显然,可以把$i,j$都前移,也就是转移到$f(i+1,j+1)$。那空格怎么处理呢?我们用$i,j$中的一个加1,另一个不变,来表示在某个字符的前面插入一个空格。 如图:

strdist

实现了插入空格,就可以书写状态转移方程了: 设$m$,$n$为字符串$A$,$B$之长度,则:

注意:在处理序列DP类问题时,尤其是多个序列的DP问题时,一定要处理边界情况! 要设计序列长度差别大的数据,并输出递推结果以检查。

有两个地方易错:

  1. 如果按照上文的状态定义,那么就一定要更新处理f[][n+1]和f[m+1][]。因为可能需要在字符串末尾补空格!
  2. 状态转移方程每一项的取得都有着条件!第一,二项只在$i$,$j$在长度范围内时取得,也就是说$i$达到了$m+1$,$j$达到了$n+1$之后就不能再前移(边界);同理,第三项是把$i$,$j$都前移,必须满足$i \leq m$且$j \leq n$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define SETINF(x) memset(x,0x3f,sizeof(x))
using namespace std;
char A[2010],B[2010];
int K,m,n,opt[2010][2010];
int main(){
    scanf("%s",A+1);scanf("%s",B+1);
    scanf("%d",&K);
    m=strlen(A+1);n=strlen(B+1);
    SETINF(opt);opt[m+1][n+1]=0;
    for(int i=m+1;i>=1;i--)
        for(int j=n+1;j>=1;j--){
            if(i<=m) opt[i][j]=min(opt[i][j],opt[i+1][j]+K);
            if(j<=n) opt[i][j]=min(opt[i][j],opt[i][j+1]+K);
            if(i<=m && j<=n) opt[i][j]=min(opt[i][j],opt[i+1][j+1]+abs(A[i]-B[j]));
        }
    printf("%d\n",opt[1][1]);
}