回分類題庫
d176: 2010 程式達人 G - DNA操作問題
出處:

Difficulity : N/A
Accepted : 14 Times | Submit :101 Times | Clicks : 1342
Accepted : 7 Users | Submit : 7 Users | Accepted rate : 100%
Time Limit :25000 ms | Memory Limit : 2000000 KBytes
題目加入時間 : 2010-05-16 19:36

Content :

DNA定序解碼目前是人類的重大工程,就連新世紀的電腦病毒也採用了基因演算法自我突變。我們從鐵頭恭大師兄的病毒語言工廠資料庫得知,他們正以這項技術大量產生不同種類的病毒。而我們對於DNA操作則還在剛起步的階段,如果我們知道某種DNA序列是優秀解毒程式的核心元件,在已有的DNA序列庫中,我們可以選一組DNA序列將其改造。改造的方法總共有三種,分別是:Insert, Delete和Replace。

舉例來說,我們知道一組DNA序列”ATAACG”是優良解讀程式的核心元件。而我們的DNA序列庫裡面有這樣的序列”ACACGG”,則我們可以透過Replace將第二個字母C替換成T(此時我們的DNA序列是”ATACGG”),在第三個字母A後面Insert一個A(此時我們的DNA序列是”ATAACGG”),並Delete最後一個字母G(此時我們的DNA序列是”ATAACG”),此時我們成功的修改我們序列庫內的DNA得到了新的優良DNA。

當然這樣的方法不是唯一的,如果我們將Insert、Delete和Replace都加上所需的花費和成本,那麼怎樣的操作過程會讓產生DNA的成本最小就是我們值得考慮的問題了。以前面的例子來說,如果Insert和Delete的代價是1,而Replace的代價是2時,總代價花費4,就是一種最小成本的花費。

Input :

輸入有會有數組測資,每組測資由一行包含三個正整數和兩行DNA字串A和B(DNA字串由英文大小寫和數字構成且長度不超過10000)。第一行的三個正整數代表了Insert、Delete和Replace的代價。

Output :

每組測資輸出一行,其內容為一個正整數,代表由A經過Insert、Delete和Replace過程後變成B,所需花費最小的代價。

Sample Input :

1 1 2
ACACGG
ATAACG
1 2 3
ISeeYou
OleNgatiKameie
1 2 4
Gintama
Kintama

Sample Output :

4
22
3

Hint :

送出次數: 3 解題率: 0

Author :


  Solve it!   Status Forum (1)

C++
C
JAVA
22026. admin ( 8.5 s , 1606244KB)
22032. pandia ( 8.6 s , 1606246KB)
21811. admin ( 8.7 s , 1606250KB)
30514. henryokc ( 11.1 s , 351700KB)
51318. uglyman ( 11.1 s , 351684KB)
56273. ag100 ( 21.2 s , 304388KB)
56277. ag100 ( 21.3 s , 304396KB)
56274. ag100 ( 21.4 s , 304390KB)
56278. ag100 ( 21.7 s , 304392KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡