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跳完、輸入序列后再進(jìn)行修改，修改的方式有三種，在任意位置插入、刪除或替換一個指令，每次插入需要a時間，刪除需要b時間，替換需要c時間，現(xiàn)在zyf想用最短時間去修改他輸入的序列得到滿分（即與給定序列一樣），但這顯然已經(jīng)超過了當(dāng)前外掛的能力范圍，于是只好求助于你，給這外掛寫個補丁。
Input
輸入包含多組數(shù)據(jù)，EOF結(jié)束。
每組數(shù)據(jù)包括三行，第一行包含三個整數(shù)a，b，c（0<a,b,c<=100)，如上文描述，第二行是跳舞毯給定的序列，第三行是zyf跳完、輸入的序列，兩者的長度都不大于1000，只包含大小寫字母。
每組數(shù)據(jù)包括三行，第一行包含三個整數(shù)a，b，c（0<a,b,c<=100)，如上文描述，第二行是跳舞毯給定的序列，第三行是zyf跳完、輸入的序列，兩者的長度都不大于1000，只包含大小寫字母。
Output
每組數(shù)據(jù)輸出一行，最少修改時間。
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內(nèi)部測試賽（Author: Qinz）
水水的動歸.第一次提交竟然沒AC,把我嚇尿了,后來發(fā)現(xiàn)把語言改成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
;
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
