https://www.luogu.com.cn/record/143177984

//kuangfengzhixi
//P1279
//dp公式：dp[i][j]=min(min(min(dp[i][j],dp[i][j-1]+k),dp[i-1][j]+k),dp[i-1][j-1]+abs(a[i]-b[j]))
#include<bits/stdc++.h>
using namespace std;
int a_size,b_size,a[100009],b[100009],dp[2009][2009],k;
string A,B;
signed main(){
    cin>>A>>B>>k;
    a_size=A.size();
    b_size=B.size();
    memset(dp,25,sizeof(dp));
    for(int i=0;i<a_size;i++){
        a[i+1]=int(A[i]);
    }
    for(int i=0;i<b_size;i++){
        b[i+1]=int(B[i]);
    }
    for(int i=1;i<=a_size;i++){
        dp[i][0]=i*k;
    }
    for(int i=1;i<=b_size;i++){
        dp[0][i]=i*k;
    }
    dp[0][0]=0;
    for(int i=1;i<=11;i++){
        for(int j=1;j<=12;j++){
            dp[i][j]=min(min(min(dp[i][j],dp[i][j-1]+k),dp[i-1][j]+k),dp[i-1][j-1]+abs(a[i]-b[j]));
        }
    }
    cout<<dp[a_size][b_size];
    return 0;
}