题解 P2453 【[SDOI2006]最短距离】

LingFengGold · 2018-09-26 16:20:25 · 题解

LingFengGold博客

宣传一下博客~~~

P2453 [SDOI2006]最短距离

状态：f[i][j]表示初始串初始串删除到第i个字符，目标串完成到第j个字符；

初始串为s1,len1；

目标串为s2,len2；

边界：

c[i][0]=cost(delet)*i；（目标串没有字符，初始串只能全删了）

c[0][j]=cost(insert)*j；（初始串一个字符都没有，目标串只能用insert一个一个插进去）

枚举i，枚举j

Copy：当a[i]==b[j]时（此条件需要判断），一样的话就copy就好；

c[i][j]=min(c[i][j],c[i-1][j-1]+cost[copy]);

Repalce：当a[i]!=b[j]时（此条件无需判断），就把初始串的删了，目标串填一个；

c[i][j]=min(c[i][j],c[i-1][j-1]+cost[replace]);

Delet：是删除一个初始串的，对于目标串无影响；

c[i][j]=min(c[i][j],c[i-1][j]+cost[delet]);

Insert：给目标串多完成一个，对初始串无影响；

c[i][j]=min(c[i][j],c[i][j-1]+cost[insert]);

Twiddle：当a[i-1]==b[j]&&a[i]==b[i-1]&&i>=2&&j>=2时（此条件需要判断），就twiddle；

c[i][j]=min(c[i][j],c[i-2][j-2]+cost[twiddle]);

枚举结束！

Kill：单独拿出来，枚举当目标串已经完成的情况下（i=len2)，初始串要清零的最小值

c[len1][len2]=min(c[len1][len2],c[i][len2]+cost[delet]*(len1-i)-1);

结果：f[len1][len2]。

上面解释的很清楚，附上代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define inf 1e18+5
#define ll long long
using namespace std;
ll inline read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char a[2050],b[2050];
ll c[2050][2050];
ll cost[6];
int main()
{
    scanf("%s%s",a+1,b+1);
    for(int i=1;i<=5;i++){
        cost[i]=read();
    }
    //1=delet,2=replace,3=copy,4=insert,5=twiddle
    int len1=strlen(a+1),len2=strlen(b+1);
    if(len1==0&&len2==0){
        printf("0");
        return 0;
    }
    if(len1==0&&len2!=0){
        printf("%lld",len2*cost[4]);
        return 0;
    }
    if(len1!=0&&len2==0){
        printf("%lld",len1*cost[1]);
        return 0;
    }
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            c[i][j]=inf;
        }
    }
    c[0][0]=0;
    for(int i=1;i<=len1;i++){
        c[i][0]=i*cost[1];
    }
    for(int i=1;i<=len2;i++){
        c[0][i]=i*cost[4];
    }
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(a[i]==b[j]){
                c[i][j]=min(c[i][j],c[i-1][j-1]+cost[3]);
            }
            c[i][j]=min(c[i][j],c[i-1][j-1]+cost[2]);
            c[i][j]=min(c[i][j],c[i-1][j]+cost[1]);
            c[i][j]=min(c[i][j],c[i][j-1]+cost[4]);
            if(i>=2&&j>=2&&a[i-1]==b[j]&&a[i]==b[j-1]){
                c[i][j]=min(c[i][j],c[i-2][j-2]+cost[5]);
            }
        }
    }
    for(int i=1;i<len1;i++){
        c[len1][len2]=min(c[len1][len2],c[i][len2]+cost[1]*(len1-i)-1);
    }
    printf("%lld",c[len1][len2]);
    return 0;
}