UC知道高手请进：动态规划 字串距离 pascal
来源：百度知道 编辑：UC知道 时间：2024/07/07 21:15:39
设有字符串x，我们称在x头尾及中间扎入任意多个空格后组成的新字串称为x的扩展串，如“abcbcd”，则"abcb_cd","_a_bcbcd_","abcb_cd_"为x的扩展串.("_"代表空格)
如果a'是a的扩展串,b'是b的扩展串,且a',b'具有相同长度,则定义a'与b'的距离为相应位置上距离总和.非空格字符间的距离为其ascll码差的绝对值,空格与字符的距离为k,空格与空格距离为零.求距离最小的a'b'
input
第一行为a
第二行为b
第三行为k
a,b长度不超过2000,k为整数在1~100内
output
a'b'最小距离
样例
input
cmc
snmn
2
output
10
请给出思路,谢谢!
也可以帮我解释一下,下面是标程:
{ DMIH 2002 - Drugi dan natjecanja }
{ Srednjoskolska skupina - II. podskupina }
{ Zadatak BLAST }
{ Autor rjesenja Ivan Sikiric }
program blast;
const maxn = 2000;
var f : text;
a, b : array[1..maxn] of byte;
g : array[0..maxn, 0..maxn] of longint;
la, lb, i, j, k, temp : longint;
c : char;
begin
assign(f, 'blast.in');
reset(f);<
如果a'是a的扩展串,b'是b的扩展串,且a',b'具有相同长度,则定义a'与b'的距离为相应位置上距离总和.非空格字符间的距离为其ascll码差的绝对值,空格与字符的距离为k,空格与空格距离为零.求距离最小的a'b'
input
第一行为a
第二行为b
第三行为k
a,b长度不超过2000,k为整数在1~100内
output
a'b'最小距离
样例
input
cmc
snmn
2
output
10
请给出思路,谢谢!
也可以帮我解释一下,下面是标程:
{ DMIH 2002 - Drugi dan natjecanja }
{ Srednjoskolska skupina - II. podskupina }
{ Zadatak BLAST }
{ Autor rjesenja Ivan Sikiric }
program blast;
const maxn = 2000;
var f : text;
a, b : array[1..maxn] of byte;
g : array[0..maxn, 0..maxn] of longint;
la, lb, i, j, k, temp : longint;
c : char;
begin
assign(f, 'blast.in');
reset(f);<
标程里面g[i,j]表示a的前i个字符的扩展串和b的前j个字符的扩展串的最短距离
现在考虑这个最短距离怎么生成的,也就是考虑这两个扩展串的最后一个字符
显然不可能都是空格,否则无视这两个空格
情况一:最后的字符分别a[i]和b[j],那么有g[i,j]=g[i-1,j-1]+(a[i],b[j]的距离)
情况二:a[i]和空格,那么有g[i,j]=g[i-1,j]+k
情况三:空格和b[j],那么有g[i,j]=g[i,j-1]+k
也就是说,g[i,j]={g[i-1,j-1]+(a[i],b[j]的距离),g[i-1,j]+k,g[i,j-1]+k}的最小值
上面的分析对应于i和j都不为0的情况
假如其中一个是0,比如j=0,显然g[i,j]=k*i,也就是这i个字符都只能和空格匹配
更显然的是g[0,0]=0
这样求出来的g[la,lb]就是最终的答案了