Problem 1005 - 跳舞毯
Time Limit
: 2000MS
Memory Limit
: 65536KB
Difficulty
:
Total Submit : 308 Accepted : 108 Special Judge : No
Total Submit : 308 Accepted : 108 Special Judge : No
Description
zyf不小心得了一种怪病，为了维持一天的精力他必须不停跳动。于是他买了一条跳舞毯，每天跳上几小时。众所周知，跳舞毯是给定一个序列，让你在指定时间踏指定的按钮，但zyf似乎不怎么擅长，为此他写了个外挂，以修改它的输入序列，得到满分！
这个外挂的厉害之处在于它能等到zyf跳完、输入序列后再进行修改，修改的方式有三种，在任意位置插入、删除或替换一个指令，每次插入需要a时间，删除需要b时间，替换需要c时间，现在zyf想用最短时间去修改他输入的序列得到满分（即与给定序列一样），但这显然已经超过了当前外挂的能力范围，于是只好求助于你，给这外挂写个补丁。
Input
输入包含多组数据，EOF结束。
每组数据包括三行，第一行包含三个整数a，b，c（0<a,b,c<=100)，如上文描述，第二行是跳舞毯给定的序列，第三行是zyf跳完、输入的序列，两者的长度都不大于1000，只包含大小写字母。
每组数据包括三行，第一行包含三个整数a，b，c（0<a,b,c<=100)，如上文描述，第二行是跳舞毯给定的序列，第三行是zyf跳完、输入的序列，两者的长度都不大于1000，只包含大小写字母。
Output
每组数据输出一行，最少修改时间。
Sample Input
1 2 3
LDDD
DDDR
7 1 3
LDDR
LZRZDD
LDDD
DDDR
7 1 3
LDDR
LZRZDD
Sample Output
3
8
8
Hint
Source
2010.04内部测试赛（Author: Qinz）
水水的动归.第一次提交竟然没AC,把我吓尿了,后来发现把语言改成C++就过了,弱菜不知为什么.
#include<stdio.h>
#include
<
string
.h>
int
f[
1010
][
1010
];
char
s1[
1010
],s2[
1010
];
int
main()
{
int
a,b,c;
while
(scanf(
"
%d%d%d
"
,&a,&b,&c)!=
EOF)
{
scanf(
"
%s%s
"
,&s2[
1
],&s1[
1
]);
int
len1=strlen(&s1[
1
]),len2=strlen(&s2[
1
]),i,j;
memset(f,
0
,
sizeof
(f));
for
(i=
0
;i<=len1;i++
)
for
(j=
0
;j<=len2;j++
)
{
if
(i==
0
&& j==
0
)
continue
;
if
(i==
0
)
{
f[i][j]
=j*
a;
continue
;
}
if
(j==
0
)
{
f[i][j]
=i*
b;
continue
;
}
int
tmp=
1000000
;
if
(f[i][j-
1
]+a<tmp) tmp=f[i][j-
1
]+
a;
if
(f[i-
1
][j]+b<tmp) tmp=f[i-
1
][j]+
b;
if
(s1[i]==
s2[j])
{
if
(f[i-
1
][j-
1
]<tmp) tmp=f[i-
1
][j-
1
];
}
else
{
if
(f[i-
1
][j-
1
]+c<tmp) tmp=f[i-
1
][j-
1
]+
c;
}
f[i][j]
=
tmp;
}
printf(
"
%d\n
"
,f[len1][len2]);
}
return
0
;
}
