Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

大哥回帖要先看啊

Posted by qddpx at 2012-08-17 00:49:19 on Problem 1080
In Reply To:经典DP,不需要那样子做 Posted by:donkeyinacm at 2010-01-26 01:18:10
> 观察题目给出的一个最优解: 
> AGTGATG 
> -GTTA-G 
> 将其从某一处切开,如果左边部分的分值不是最大,那么将其进行调整,使其分值变大,则整个解分值变大,与已知的最优矛盾。所以左边部分的分值必是最大。同理,右边也是。可见满足最优子结构的性质。考虑使用DP: 
> 
> 设两个DNA序列分别为s1,s2,长度分别为len1,len2,score为分值表。f[i,j]表示子串s1[1..i]和s2[1..j]的分值。考虑一个f[i,j],我们有: 
> 1.s1取第i个字母,s2取“-”:f[i-1,j] + score[s1[i],'-'] 
> 2.s1取“-”,s2取第j个字母:f[i,j-1] + score['-',s2[j]] 
> 3.s1取第i个字母,s2取第j个字母:f[i-1,j-1] + score[s1[i],s2[j]] 
> 即f[i,j] = max(f[i-1,j] + score[s1[i],'-'], f[i,j-1] + score['-',s2[j]], f[i-1,j-1] + score[s1[i],s2[j]]); 
> 
> 然后考虑边界条件,这道题为i或j为0的情况。 
> 当i=j=0时,即为f[0,0],这是在计算f[1,1]时用到的,根据f[1,1] = f[0,0] + score[s1[i], s2[j]],明显有f[0,0] = 0。 
> 当i=0时,即为f[0,1..len2],有了f[0,0],可以用f[0,j] = f[0,j-1] + table['-',s2[j]]来计算。 
> 当j=0时,即为f[1..len1,0],有了f[0,0],可以用f[i,0] = f[i-1,0] + table[s1[i],'-']来计算。 
> 
> 至于计算顺序,只要保证计算f[i,j]的时候,使用到的f[i-1,j],f[i,j-1],f[i-1,j-1]都计算出来了就行了。所谓划分阶段也就是为了达到这个目的。这样我们使用一个二重循环就可以了。
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator