P1046 （C++代码）

解题思路:





注意事项:





参考代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int A[2010][2010];
char s1[2010];
char s2[2010];
int len1,len2;
int k;
void dp()
{    
for(int i=1;i<=len1;i++)
    {        
    for(int j=1;j<=len2;j++)
        {
            A[i][j]=min(A[i-1][j]+k,min(A[i][j-1]+k,A[i-1][j-1]+abs((int)s1[i]-(int)s2[j])));
        }
    }
}
void ini()   //需要一点点预处理 
{    for(int i=1;i<=len1;i++)
    {
         A[i][0]=A[i-1][0]+k;
    }    for(int i=1;i<=len2;i++)
    {
        A[0][i]=A[0][i-1]+k;
    }
}
    int main()
    {    
    cin>>s1+1;    
    cin>>s2+1;    
    cin>>k;
    len1=strlen(s1+1);
    len2=strlen(s2+1);
    ini();
    dp();    
    printf("%d",A[len1][len2]);    
    return 0;
}