题解 UVA1207 【AGTC】

sdxjzsq

2020-03-19 23:50:35

Solution

### 题目链接 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; } ```