作者march20 ()
看板Programming
标题Re: [问题] dna序列密度
时间Mon May 18 15:59:41 2009
※ 引述《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
1F：→ march20:咦, 这样好像就是原 po 说的暴力法 XD 66.75.255.220 05/18 16:18
2F：→ TonyQ:dp 只是把省掉子问题重复计算的时间 ,本质 221.169.78.140 05/19 06:33
3F：→ TonyQ:还是列举法没错啊. :p 221.169.78.140 05/19 06:33