NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2015國中組決賽
 npsc2015-國中組決賽 C. 頗汪上生物課

作者 主題: npsc2015-國中組決賽 C. 頗汪上生物課  (閱讀 988 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
npsc2015-國中組決賽 C. 頗汪上生物課
« 於: 一月 13, 2016, 08:04:05 pm »

我覺得解法應是兩兩字串的 (長度和 - LCS ) 找最小的
例如第1組測資
ATTCCG
4
ATG
CGA
ATTCC
TC
(1) ATTCCG+ATG長度和為9 - 3{LCS(ATTCCG,ATG) = 6
(2) ATTCCG+CGA長度和為9 - 2{LCS(ATTCCG,CGA) = 7
(3) ATTCCG+ATTCC長度和為11 - 5{LCS(ATTCCG,ATTCC) = 6
(4) ATTCCG+TC長度和為8 - 2{LCS(ATTCCG,ATG) = 6

例如第2組測資
TCGAATTGCA
2
AAAAAAAAAAAAAAAA
GGGGGGGGGGGGGGGG
(1) TCGAATTGCA+AAAAAAAAAAAAAAAA長度26 - 3{LCS(TCGAATTGCA,AAAAAAAAAAAAAAAA) = 23
(2) TCGAATTGCA+GGGGGGGGGGGGGGGG長度26 -2{LCS(TCGAATTGCA,GGGGGGGGGGGGGGGG) = 24

字串長度各 5000 ,忘了LCS的時間怎麼算了,只算長度應該沒問題
« 上次編輯: 一月 14, 2016, 08:37:17 pm 由 rscpp »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2015國中組決賽
 npsc2015-國中組決賽 C. 頗汪上生物課