#include <iostream>
#include <cmath>
using namespace std;

const int maxn = 2010;
int dp[maxn][maxn];

int main() {
    ios::sync_with_stdio(false);
    string s1, s2;
    int k;
    while (cin >> s1 >> s2 >> k) {
        int n = s1.length(), m = s2.length();
        for (int i = 1; i <= n; i++)
            dp[i][0] = i * k;
        for (int i = 1; i <= m; i++)
            dp[0][i] = i * k;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]) + k, dp[i - 1][j - 1] + (int)abs(s1[i - 1] - s2[j - 1]));
        cout << dp[n][m] << endl;
    }
    return 0;
}
#include <iostream>
#include <cmath>
using namespace std;

const int maxn = 2010;
int dp[maxn][maxn];

int main() {
    ios::sync_with_stdio(false);
    string s1, s2;
    int k;
    while (cin >> s1 >> s2 >> k) {
        int n = s1.length(), m = s2.length();
        for (int i = 1; i <= n; i++)
            dp[i][0] = i * k;
        for (int i = 1; i <= m; i++)
            dp[0][i] = i * k;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]) + k, dp[i - 1][j - 1] + (int)abs(s1[i - 1] - s2[j - 1]));
        cout << dp[n][m] << endl;
    }
    return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 16340 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 16344 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 16340 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 16340 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 16344 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 16344 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 16340 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 16340 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 16340 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 16340 KiB, score = 10

Accepted, time = 76 ms, mem = 16344 KiB, score = 100
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
const int maxn=2000+7;
int f[maxn][maxn],a[maxn],b[maxn],k,lena,lenb;
char al[maxn],bl[maxn];
int main()
{
// freopen("in.txt","r",stdin);
scanf("%s",al);
scanf("%s",bl);
lena=strlen(al);lenb=strlen(bl);
scanf("%d",&k);
rep(i,lena)a[i]=al[i-1];
rep(i,lenb)b[i]=bl[i-1];
f[0][0]=0;
rep(i,lena)f[i][0]=f[i-1][0]+k;
rep(i,lenb)f[0][i]=f[0][i-1]+k;
rep(i,lena)
rep(j,lenb)
f[i][j]=min(f[i-1][j-1]+abs(a[i]-b[j]),min(f[i-1][j],f[i][j-1])+k);
printf("%d",f[lena][lenb]);
return 0;
}

不不不

代码+题解

AC99纪念
测试数据 #0: Accepted, time = 15 ms, mem = 16544 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 16544 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 16580 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 16652 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 17108 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 16804 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 16828 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 16824 KiB, score = 10
测试数据 #8: Accepted, time = 93 ms, mem = 16832 KiB, score = 10
测试数据 #9: Accepted, time = 125 ms, mem = 16856 KiB, score = 10
Accepted, time = 418 ms, mem = 17108 KiB, score = 100
------------------------------华丽的分割线------------------------------
```pascal
type int=longint;
var
s1,s2:ansistring;
l1,l2,k:int;
a:array[0..2000,0..2000]of int;
function min(x,y,z:int):int;
begin
min:=x;
if y<min then min:=y;
if z<min then min:=z;
exit(min);
end;

function f(x,y:int):int;
begin
if a[x,y]>0 then exit(a[x,y]);
if (x=0)or(y=0) then exit((x+y)*k);
f:=min(f(x-1,y-1)+abs(ord(s1[x])-ord(s2[y])),f(x-1,y)+k,f(x,y-1)+k);
a[x,y]:=f;
end;

begin
readln(s1);
readln(s2);
readln(k);
l1:=length(s1);
l2:=length(s2);
fillchar(a,sizeof(a),0);
writeln(f(l1,l2));
end.
```
我在**秋名山**等你！！！

var
s1,s2:ansistring;
a:array [0..2100,0..2100] of longint;
k,l1,l2,i,j:longint;
function min(x,y:longint):longint;
begin if (x<y) then exit(x) else exit(y); end;
begin
readln(s1);
readln(s2);
read(k);
l1:=length(s1);
l2:=length(s2);
fillchar(a,sizeof(a),10);
for i:=0 to l1 do a[i,0]:=i*k;
for i:=0 to l2 do a[0,i]:=i*k;
for i:=1 to l1 do
for j:=0 to l2 do
a[i,j]:=min(a[i-1,j-1]+abs(ord(s1[i])-ord(s2[j])),min(a[i-1,j]+k,a[i,j-1]+k));
writeln(a[l1,l2]);
end.

预处理好纠结

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;

char c[3000],d[3000];
char a[3000],b[3000];
int f[2100][2100];

int main()
{
cin>>c>>d;
int k;
cin>>k;
int lena=strlen(c);
int lenb=strlen(d);
for(int i=1; i<=lena; i++)
a[i]=c[i-1];
for(int i=1; i<=lenb; i++)
b[i]=d[i-1];
for(int i=1; i<=lena; i++)
f[i][0]=f[i-1][0]+k;
for(int j=1; j<=lenb; j++)
f[0][j]=f[0][j-1]+k;
for(int i=1; i<=lena; i++)
for(int j=1; j<=lenb; j++)
f[i][j] = min(f[i-1][j-1]+abs(a[i]-b[j]),min(f[i-1][j],f[i][j-1])+k);

cout<<f[lena][lenb];
return 0;
}

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
char a[2005],b[2005];
int f[2005][2005];
int lena,lenb,k;
void Init(){
char ch;
lena=lenb=0;
while(scanf("%c",&ch)&&(ch<='z')&&(ch>='a'))
a[++lena]=ch;
while(scanf("%c",&ch)&&(ch<='z')&&(ch>='a'))
b[++lenb]=ch;
scanf("%d",&k);
}
int main(){
//freopen("p1.in","r",stdin);
Init();
for(int i=1;i<=lena;i++)
f[i][0]=f[i-1][0]+k;
for(int i=1;i<=lenb;i++)
f[0][i]=f[0][i-1]+k;
for(int i=1;i<=lena;i++)
for(int j=1;j<=lenb;j++)
f[i][j]=min(f[i-1][j-1]+abs(a[i]-b[j]),min(f[i-1][j],f[i][j-1])+k);
printf("%d",f[lena][lenb]);
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 16336 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 16344 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 16340 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 16336 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 16340 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 16344 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 16340 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 16340 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 16344 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 16340 KiB, score = 10
Accepted, time = 214 ms, mem = 16344 KiB, score = 100
代码
#include <cstdio>
#include <cstring>
#include <algorithm>

#define M 2000+10

using namespace std;

int dp[M][M],sl,ssl,k;
char s[M],ss[M];

int main() {
scanf("%s",s);scanf("%s",ss);scanf("%d",&k);
sl = strlen(s);ssl = strlen(ss);
memset(dp,0,sizeof(dp));
dp[0][0]=0;
for(int i = 1; i <=sl; i++) dp[i][0] = dp[i-1][0]+k;
for(int i = 1; i <=ssl; i++) dp[0][i] = dp[0][i-1]+k;
for(int i = 1; i <= sl; i++) {
for(int j = 1; j <= ssl; j++) {
dp[i][j] = dp[i-1][j-1] + abs(s[i-1]-ss[j-1]);
dp[i][j] = min(dp[i][j],min(dp[i-1][j]+k,dp[i][j-1]+k));
}
}
printf("%d",dp[sl][ssl]);
return 0;
}

program p1680;
var s1,s2:ansistring;
i,j,k:longint;
f:array[0..2000,0..2000] of longint;
//
function min(a,b,c:longint):longint;
begin
min:=10000;
if a<min then min:=a;
if b<min then min:=b;
if c<min then min:=c;
end;
//
begin
readln(s1);
readln(s2);
readln(k);
for i:=1 to length(s2) do f[0,i]:=i*k;
for i:=1 to length(s1) do f[i,0]:=i*k;
for i:=1 to length(s1) do
for j:=1 to length(s2) do
f[i,j]:=min(f[i,j-1]+k,f[i-1,j]+k,f[i-1,j-1]+abs(ord(s1[i])-ord(s2[j])));
write(f[i,j]);
end.

var s1,s2:ansistring;
l1,l2,i,j,k:longint;
f:array[0..2001,0..2001] of int64;
function min(x,y,z:int64):int64;
begin
min:=x;
if y<min then min:=y;
if z<min then min:=z;
end;
begin
readln(s1);l1:=length(s1);
readln(s2);l2:=length(s2);
readln(k);
f[0,0]:=0;
for i:=1 to l1 do f[i,0]:=f[i-1,0]+k;
for i:=1 to l2 do f[0,i]:=f[0,i-1]+k;
for i:=1 to l1 do
for j:=1 to l2 do
f[i,j]:=min(f[i-1,j]+k,f[i,j-1]+k,f[i-1,j-1]+abs(ord(s1[i])-ord(s2[j])));
writeln(f[l1,l2]);
end.
怎么才能秒杀！orz大神！

不知道为什么楼下的人都说这题很水，虽然我也一边AC，但至少我也思考了好一会才意识到的。
一看题目就知道是DP。但刚开始方程没有往LCS这边想，而是往1264那题类似的方程想，导致花了一段无用功。。
经过单步调试以后，发现了错误。才想到了LCS，方程也非常简单：
f[i,j]:=min(f[i-1,j-1]+num,//i,j这两个数选取
f[i-1,j]+k
f[i,j-1]+k //用空格。

剩下就是要处理边界，比较适合练手。

DXE—SYF

【分析】本题是一道典型的线性动归。

首先考虑阶段的划分，A、B两串前面连续多少个字符是具备明显后效性的，也就是说取A的前i个和B的前j个所计算出来的最优值与后面如果引用此结构怎么放是没有影响的，所以用A的前I个和B的前J个连续字符来划分阶段是正确的，因为两串长度都不超2000，2000^2不会超时。

下面来考虑情况：f要么把a[i]配到一起b[j]，则有f+a[i]和b[j]间的距离，如果不配到一起，就把a[i]或b[j]中的一个单独处理加k值。

【方程】F=Min{f+abs(ord(a[i])-ord(b[j])),f+k,f+k}

参考程序见我的博客http://zhurui250.blog.163.com/blog/static/137270520201021152918767/edit/

var

a:array[0..2000,0..2000] of integer;

i,j,k,g1,g2:integer;

s1,s2:string;

function f(n1,n2,n3:integer):integer;

begin

if n1>n2

then f:=n2

else f:=n1;

if n1>n3

then f:=n3;

end;

begin

readln(s1);

readln(s2);

readln(k);

g1:=length(s1);

g2:=length(s2);

for i:=1 to g1 do

a:=i*k;

for j:=1 to g2 do

a[0,j]:=j*k;

for i:=1 to g1 do

for j:=1 to g2 do

a:=f(a+abs(ord(s1[i])-ord(s2[j])),a+k,a+k);

writeln(a);

readln;

end.

哪里错了啊

!!!!!!!!

用f表示A的前i位和B的前j位进行比较时，所取得的最小值。

则有f=min{f+k , f+k , f+abs(ord(A[i])-ord(B[j]))}

program p1680;

var a,b:string;k,i,j,n1,n2:integer;

f:array[0..2003,0..2003] of integer;

begin

readln(input,a);

readln(input,b);

readln(input,k);

n1:=length(a); n2:=length(b);

for i:= 1to n1 do f:=k+f;

for j:= 1to n2 do f[0,j]:=f[0,j-1]+k;

for i:= 1to n1 do

for j:= 1 to n2 do

begin

f:=f+abs(ord(a[i])-ord(b[j]));

if f>f+k then f:=f+k;

if f>f+k then f:=f+k;

end;

write(f[n1,n2]);

end.

哪错了？ 怎么才40？

三次才AC....我有罪..

问大家两个问题...

为什么一开始要吧F,F[0,J]都处理好?只处理F[0,1],F[1,0]不可以吗?

还有,为什么一开始全赋0...不是应该赋正无穷吗?

399+1同学，注意ansistring

第一次把范围搞错了