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 ; }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
