| 题目名称 | 375. 字符串的距离 |
|---|---|
| 输入输出 | blast.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2009-09-16加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：132， 提交：197， 通过率：67.01% | ||||
 TARDIS |
100 | 0.033 s | 7.87 MiB | C++ |
 _Itachi |
100 | 0.036 s | 0.33 MiB | C++ |
 BaDBoY |
100 | 0.042 s | 7.79 MiB | C++ |
 jhs |
100 | 0.082 s | 15.65 MiB | C++ |
 黑夜<=>白天 |
100 | 0.083 s | 15.73 MiB | C++ |
 面对疾风吧 疾风 疾风吧 |
100 | 0.087 s | 14.15 MiB | C++ |
 kito |
100 | 0.087 s | 15.70 MiB | C++ |
 隨風巽 |
100 | 0.088 s | 15.73 MiB | C++ |
 HeRaNO |
100 | 0.088 s | 15.80 MiB | C++ |
 liu_runda |
100 | 0.090 s | 15.63 MiB | C++ |
| 本题关联比赛 | |||
| 20090916练习赛 | |||
| 20090916练习赛 | |||
| 20090916练习赛 | |||
| 20090916练习赛 | |||
| 专项训练十题 | |||
| 关于 字符串的距离 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
g[i, j]=Min{g[i-1, j]+k, g[i, j-1]+k, g[i-1, j-1]+aibi } 0≤i≤La 0≤j≤Lb
其中，k为空格与字符之间的距离； aibi为字符ai与字符bi的距离。 初始值：g[0, 0]=0 g[0, j]=j·k g[i, 0]=i·k | ||||
|
| ||||
|
楼上所说题目题库已有。。。
 苏轼
2012-10-18 19:47
2楼
| ||||
|
现实意义：一个一个用字母填空，现在，第一个串填到i处，第二个串填到j处
三种情况： 1、此两空填s1[i]和“空” 2、此两空填“空”和s2[j] 3、此两空填s1[i]和s2[j] 类似题目：编辑距离（PID：题库暂无此题），最长公共子序列长度（PID：476），相似基因（PID：366）…… | ||||
AntiLeaf
Zwoi_只会打表抄代码的蒟蒻
啊吧啦吧啦吧
Truth.Cirno
设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。
如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为O。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。
请你写一个程序，求出字符串A、B的距离。
输入
输入文件第一行为字符串A，第二行为字符串B，A、B均由小写字母组成且长度均不超过2000，第三行为一个整数K，1≤K≤100，表示空格与其它字符的距离。
输出
输出文件仅一行包含一个整数，表示要求的字符串A、B的距离。
输入样例
cmc
snmn
2
输出样例
10