M_sea

洛谷2453 [SDOI2006]最短距离
Luogu分析两个字符串,求最小变换次数,显然是DP。设$a[]$为目标串,$b[]$为原串。然后设$f[i][j...
扫描右侧二维码阅读全文
20
2018/10

洛谷2453 [SDOI2006]最短距离

Luogu

分析

两个字符串,求最小变换次数,显然是DP。

设$a[]$为目标串,$b[]$为原串。
然后设$f[i][j]$表示$a$已产生$i$个,$b$已删除$j$个的最小代价。

边界很显然:

$$f[i][0]=i*cost(insert)$$

$$f[0][i]=i*cost(delete)$$

然后五种操作分开转移:

  • 删除:

$$f[i][j]=f[i][j-1]+cost(delete)$$

  • 替换(需要注意的是可以替换成相同的字符)

$$f[i][j]=f[i-1][j-1]+cost(replace)$$

  • 复制(需要$a[i]=b[j]$才可转移)

$$f[i][j]=f[i-1][j-1]+cost(copy)\quad (a[i]=b[j])$$

  • 插入

$$f[i][j]=f[i-1][j]+cost(insert)$$

  • 交换并复制(需要$i\geq2$并且$j\geq2$并且$a[i]=b[j-1]$并且$a[i-1]=b[j]$才可转移)

$$f[i][j]=f[i-2][j-2]+cost(twiddle)\quad \text{条件如上}$$


最后处理kill,但是$f[length_a][length_b]$不用kill。

答案即为$min_{i=1}^{length_b}f[length_a][i]$。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline void chmin(int& a,int b) { if (b<a) a=b; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

char a[210],b[210]; //a是目标串,j是原串 
int del,rep,cop,ins,twi;

int f[210][210]; //f[i][j]表示a已产生i个,b已删除j个的最小代价 

int main() {
    cin>>b+1>>a+1; int n=strlen(a+1),m=strlen(b+1);
    del=read(),rep=read(),cop=read(),ins=read(),twi=read();
    for (re int i=1;i<=n;i++) f[i][0]=i*ins;
    for (re int i=1;i<=m;i++) f[0][i]=i*del;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++) {
            f[i][j]=2147483647;
            chmin(f[i][j],f[i][j-1]+del);
            chmin(f[i][j],f[i-1][j-1]+rep);
            if (a[i]==b[j]) chmin(f[i][j],f[i-1][j-1]+cop);
            chmin(f[i][j],f[i-1][j]+ins);
            if (a[i]==b[j-1]&&a[i-1]==b[j]&&i>1&&j>1) chmin(f[i][j],f[i-2][j-2]+twi);
        }
    int ans=f[n][m];
    for (re int i=1;i<m;i++)
        chmin(ans,f[n][i]+(m-i)*del-1);
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 51 PM

发表评论