题解
#include
<
fstream
>
using
namespace
std;
int
n1,n2,k;
string
s1,s2;
int
f[
2001
][
2001
];
int
main()
{
ifstream cin(
"
blast.in
"
);
ofstream cout(
"
blast.out
"
);
cin
>>
s1
>>
s2
>>
k;
f[
0
][
0
]
=
0
;
n1
=
s1.size();
n2
=
s2.size();
for
(
int
i
=
1
;i
<=
n1;
++
i)
f[i][
0
]
=
f[i
-
1
][
0
]
+
k;
for
(
int
i
=
1
;i
<=
n2;
++
i)
f[
0
][i]
=
f[
0
][i
-
1
]
+
k;
for
(
int
i
=
1
;i
<=
n1;
++
i)
for
(
int
j
=
1
;j
<=
n2;
++
j){
if
(f[i
-
1
][j]
+
k
>
f[i][j
-
1
]
+
k)
f[i][j]
=
f[i][j
-
1
]
+
k;
else
f[i][j]
=
f[i
-
1
][j]
+
k;
if
(f[i][j]
>
abs(s1[i
-
1
]
-
s2[j
-
1
])
+
f[i
-
1
][j
-
1
])
f[i][j]
=
abs(s1[i
-
1
]
-
s2[j
-
1
])
+
f[i
-
1
][j
-
1
];
}
cout
<<
f[n1][n2]
<<
endl;
return
0
;
}
posted on 2009-04-15 14:45
xfstart07 阅读(179)
评论(0) 编辑 收藏 引用 所属分类:
代码库