→ march20:咦, 這樣好像就是原 po 說的暴力法 XD 66.75.255.220 05/18 16:18
→ TonyQ:dp 只是把省掉子問題重複計算的時間 ,本質 221.169.78.140 05/19 06:33
→ TonyQ:還是列舉法沒錯啊. :p 221.169.78.140 05/19 06:33
※ 引述《march20 ()》之銘言：
: ※ 引述《makiyolove (暴力熊)》之銘言：
: : 在網路上看到的題目
: : DNA序列是由A、T、C、G組成一串字串序列
: : 舉例:agGCTGCAatGACAGTTGGG
: : 然後找出大於使用者輸入長度L
^^^^
: : 包含C、G密度最高的序列串
: : 此題解應輸出gGCTGC (假設L=5)
: : 我只有想到用暴力法
: : 列出每一種組合 計算密度 比較大小 再輸出
: : 應該有更快的方法可以用?
: : 懇請板友指教
: 字串為 A[1..n]
: 1: 令 S[0] = 0, 求 S[i] = #CG in A[1..i] for 0 < i <= n
: 2: 求出哪個 L < i <= n 有最大的 S[i] - S[i-L]
: 結束
啊, 眼殘看錯, 那會麻煩點, 變成要求 (S[i] - S[j])/(i-j) 的最大,
不過還是 DP 就是了 XD
--
exception
divide error
page fault
invalid instruction
general protection fault
fatal exception
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 66.75.255.220