题解：P2453 [SDOI2006] 最短距离

Description

给你两个字符串

s_1,s_2

再给你一系列变换操作每种操作有一定的花费，求将

s_1

转换为

s_2

的最小花费。

Solution

对于这种字符串操作的题，显而易见就是 dp 了。

定义

f_{i,j}

为将原串处理到第

i

位，目标串处理到第

j

位的最小花费。

根据定义可得：

对于 delete 操作显然有 f[i][j]=min(f[i][j],f[i-1][j]+cost_delete)。
对于 insert 操作显然有 f[i][j]=min(f[i][j],f[i][j-1]+cost_insert)。
对于 replace 操作显然有 f[i][j]=min(f[i][j],f[i-1][j-1]+cost_replace)。
当 s1[i]=s2[j] 时可以使用操作 copy，显然有 f[i][j]=min(f[i][j],f[i-1][j-1]+cost_copy)。
当 s1[i]=s2[j-1] 且 s1[i-1]=s2[j] 时可以使用操作 twiddle，显然有 f[i][j]=min(f[i][j],f[i-2][j-2]+cost_twiddle)。

关于操作 kill 显然只用转移

f_{i,m}

到

f_{n,m}

，也就是 f[n][m]=min(f[n][m],f[i][m]+cost_delete*(n-i)-1)。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=205; 
string s1,s2;
int n,m; 
int f[N][N];
int de,re,cy,ir,td;

int main(){
    cin>>s1>>s2;
    n=s1.size(),m=s2.size();
    s1="~"+s1,s2="!"+s2;
    cin>>de>>re>>cy>>ir>>td;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            f[i][j]=1e9;
    f[0][0]=0;
    for(int i=1;i<=n;i++) f[i][0]=i*de;//注意初始化
    for(int j=1;j<=m;j++) f[0][j]=j*ir;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s1[i]==s2[j])
                f[i][j]=min(f[i][j],f[i-1][j-1]+cy);
            f[i][j]=min(f[i][j],f[i-1][j-1]+re);
            f[i][j]=min(f[i][j],f[i-1][j]+de);
            f[i][j]=min(f[i][j],f[i][j-1]+ir);
            if(i>=2 && j>=2 && s1[i]==s2[j-1] && s1[i-1]==s2[j])
                f[i][j]=min(f[i][j],f[i-2][j-2]+td);
        }
    }
    for(int i=1;i<n;i++)
	        f[n][m]=min(f[n][m],f[i][m]+de*(n-i)-1);
    cout<<f[n][m];
    return 0;
}

题解：P2453 [SDOI2006] 最短距离

文章操作

Description

Solution

Code

相关推荐

评论

题解：P2453 [SDOI2006] 最短距离