题解 UVA1207 【AGTC】
sdxjzsq
2020-03-19 23:50:35
### 题目链接
https://www.luogu.com.cn/problem/UVA1207
http://poj.org/problem?id=3356
### 题意
已知字符串$x$和$y$,求通过删除$x$的某个字符,在$x$中增加某个字符,更改$x$上的某个字符三种操作得到$y$的最小操作次数。
### 思路
这个题算是字符串DP最小编辑距离板子题了。
设$dp[i][j]$表示$x$的前$i$位和$y$的前$j$位的最小编辑距离。
那么如果$x[i]==y[j]$,那么$dp[i][j]=dp[i-1][j-1]$,否则$dp[i][j]$则会通过题目中的三种操作转移过来:
1. 当替换$x[i]$时,$dp[i][j]=dp[i-1][j-1]+1$
2. 当在x[i]后面增加一个字符时,$dp[i][j]=dp[i][j-1]+1$
3. 当删去x[i]时,$dp[i][j]=dp[i-1][j]+1$
以上三种操作取最小值即可得到$dp[i][j]$的DP转移方程:
$$
dp[i][j]=\begin{cases}dp[i-1][j-1] & x[i]=y[j]\\
min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1&x[i]\neq y[j]\end{cases}
$$
### Tips
1. 本题是多测
2. 记得初始化边界$dp[1..n][0]$和$dp[0][1..m]$的值,也就是在$x$先增加一些字符($dp[i][0]=i$)和删除$x$最前面的一些字符($dp[0][j]=j$)
### code
``` cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1005;
int n,m,dp[maxn][maxn];
char x[maxn],y[maxn];
int main()
{
while(scanf("%d%s%d%s",&n,x+1,&m,y+1)!=EOF)
{
for(register int i=1;i<=n;i++)dp[i][0]=i;
for(register int j=1;j<=m;j++)dp[0][j]=j;
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
dp[i][j]=dp[i-1][j-1]+(x[i]==y[j]?0:1),
dp[i][j]=min(dp[i][j],dp[i-1][j]+1),
dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
printf("%d\n",dp[n][m]);
}
return 0;
}
```