CodeForces - 56D Changing a String(dp)

Posted on | In , ,

思路

第一反应是最长公共子序列乱搞。。显然不对啊
我们令dp[i][j]为从s1(1,i)转换到s2(1,j)所需要的最少步数。分四种情况讨论:

  1. 插入：dp[i][j]=min(dp[i][j],dp[i][j-1]+1)，我们已经知道从s1(1,i)转换到s2(1,j-1)，所以在j-1尾插入字来尝试更新dp[i][j]
  2. 删除：dp[i][j]=min(dp[i][j],dp[i-1][j]+1)，我们已经知道从s1(1,i-1)转换到s2(1,j)，因为已经转换完成，所以i比之前i-1的状态只需要删去一个字符就能变成s2(1,j)
  3. 替换：dp[i][j]=dp[i-1][j-1]+1，转移显而易见
  4. 不变：dp[i][j]=dp[i-1][j-1],同样是转移显而易见。

最后打印路径即可，因为这里操作可逆

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define ll long long
#define INF 0x7fffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))

using namespace std;

char s1[1050],s2[1050];
int dp[1050][1050];

int main() {
    while(~scanf("%s",s1)){
        scanf("%s",s2);
        int n=strlen(s1),m=strlen(s2);
        dp[0][0]=0;
        for(int i=1;i<=n;i++)dp[i][0]=i;
        for(int i=1;i<=m;i++)dp[0][i]=i;
        for(int i=1;i<=strlen(s1);i++){
            for(int j=1;j<=strlen(s2);j++){
                dp[i][j]=INF;
                if(j&&dp[i][j-1]+1<dp[i][j])dp[i][j]=dp[i][j-1]+1;
                if(i&&dp[i-1][j]+1<dp[i][j])dp[i][j]=dp[i-1][j]+1;
                if(i&&j&&dp[i-1][j-1]+1<dp[i][j])dp[i][j]=dp[i-1][j-1]+1;
                if(i&&j&&s1[i-1]==s2[j-1]&&dp[i-1][j-1]<dp[i][j])dp[i][j]=dp[i-1][j-1];
            }
        }
        printf("%d\n",dp[n][m]);
        while(n>0||m>0){
            if(m&&dp[n][m-1]+1==dp[n][m]){
                printf("INSERT %d %c\n",n+1,s2[m-1]);
                m--;
            }
            else if(n&&dp[n-1][m]+1==dp[n][m]){
                printf("DELETE %d\n",n);
                n--;
            }
            else if(m&&n&&dp[n-1][m-1]+1==dp[n][m]){
                printf("REPLACE %d %c\n",n,s2[m-1]);
                n--,m--;
            }
            else n--,m--;
        }
    }
	return 0;
}