题解：P2453 [SDOI2006] 最短距离

_std_O2 · 2025-10-04 16:29:48 · 题解

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

#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;
}