e092. Q-6-8. Local alignment - 花中程式設計挑戰系統

Content

輸入兩字串，計算 local alignment 的最大分數。評分機制為：兩字母相同得 8 分，相異-5 分，字母與空白對應-3 分。

Time limit: 1 秒

Input

第一行與第二行各有一個字串，字串均只由 ATCG 四個字母組成，長度不超過 500。

Output

Local alignment 的最大分數。

Sample Input

範例一：
ATATCTTAACTGG
CGCGGATCATAA

範例二：
AAAACTGAGGG
GGCTATT

Sample Output

範例一：
43

範例二輸出：
21

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

Hint ：

範例一說明：第一個字串取 ATCTTAA，第二個取 ATCATAA。

範例二說明：第一個字串取 CTGA，第二個取 CTA。

提示：計算 global alignment 與 LCS 很類似，計算 local alignment 與 global 的差別在於：可以”昨日種種譬如昨日死”，DP 過程中，如果前面的分數不好，可以放棄繼承，此外，最大分數未必出現在最後的位置。

Tags:

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」