20200301集训练习题

· · 个人记录

P2758 编辑距离

这显然是一道DP题，我们定义 dp[i][j] 为字符串 a 匹配到 i ，字符串 b 匹配到 j 时需要用的最小操作次数，状态就定义完了。

我们来写状态转移方程，它给了三个操作，因此我们根据它来推式子

1、删除一个字符；

dp[i][j] = \min(dp[i][j-1]+1)

2、插入一个字符；

dp[i][j] = \min(dp[i-1][j]+1)

3、将一个字符改为另一个字符；我们显然要修改成与对应字符相同的字符。

dp[i][j] = \min(dp[i-1][j-1]+1)

4、如果自然就匹配上了，那么直接转移。

dp[i][j] = \min(dp[i-1][j-1])

核心代码：

memset(dp,127,sizeof(dp));
dp[0][0] = 0;
for(int i = 0;i <= lb;i ++){
    for(int j = 0;j <= la;j ++){
        if(j) dp[i][j] = dp[i][j-1]+1;
        if(i) dp[i][j] = min(dp[i][j],dp[i-1][j] + 1);
        if(i&&j) dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1);
        if(i&&j) if(a[j] == b[i]) dp[i][j] = min(dp[i][j],dp[i-1][j-1]);
    }
}

对于Beer Game我们发现就是多了一些数字，要求这些数字必须要全部转化回字符，其余处理与洛谷上的这道题几乎一样。

我们可以首先将所有数字打开来，预处理出没有数字的字符串，新加的字符用特殊标识占位。然后我们将上一题的第四个转移方程中的 == 处理一下，使得不仅两边相等时直接转移，任意一边是新添加的特殊字符时也直接转移。

虽然题目说我们可以在两个字符串上进行添加和删除操作，但是想一想，在 a 上添加等价于在 b 上删除，同理在 a 上删除等价于在 b 上添加，因此我们可以只修改 b 串，得到的答案仍然是正解。

核心代码：

memset(dp,76,sizeof(dp));
dp[0][0] = 0;
for(int i = 0;i <= lb;i ++){
    for(int j = 0;j <= la;j ++){
        if(j) dp[i][j] = dp[i][j-1]+1;
        if(i) dp[i][j] = min(dp[i][j],dp[i-1][j] + 1);
        if(i&&j) dp[i][j] = min(dp[i][j],dp[i-1][j-1]+2);
        if(i&&j) if(s1[j] == s2[i] || (s1[j]==0 || s2[i]==0)) dp[i][j] = min(dp[i][j],dp[i-1][j-1]);
    }
}

可以看出，两份代码的核心内容基本一致。

完整代码：


 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>

using namespace std;
const int N=2e4+7,M=2e3+7;
char a[N],b[M];
int la,lb,cnta,cntb;
int dp[M][N];
int s1[N],s2[N];
int tmp = 0;
int main()
{
    scanf("%s %s",a+1,b+1);
    la = strlen(a+1);lb = strlen(b+1);
    for(int i = 1;i <= la;i ++){
        if(isdigit(a[i])){
            tmp ++;
            for(int j = '1';j <= a[i];j ++) s1[++cnta] = 0;
        }
        else s1[++cnta] = a[i];
    }
    for(int i = 1;i <= lb;i ++){
        if(isdigit(b[i])){
            tmp ++;
            for(int j = '1';j <= b[i];j ++) s2[++cntb] = 0;
        }
        else s2[++cntb] = b[i];
    }
    la = cnta,lb = cntb;
    memset(dp,76,sizeof(dp));
    dp[0][0] = 0;
    for(int i = 0;i <= lb;i ++){
        for(int j = 0;j <= la;j ++){
            if(j) dp[i][j] = dp[i][j-1]+1;
            if(i) dp[i][j] = min(dp[i][j],dp[i-1][j] + 1);
            if(i&&j) dp[i][j] = min(dp[i][j],dp[i-1][j-1]+2);
            if(i&&j) if(s1[j] == s2[i] || (s1[j]==0 || s2[i]==0)) dp[i][j] = min(dp[i][j],dp[i-1][j-1]);
        }
    }
    printf("%d",dp[lb][la]+tmp);
    return 0;
}