【POJ1080】Human Gene Functions(动态规划 最长公共子序列)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 22 日
//解题思路:  
//和《算法导论》中动态规划章节的LCS(Longest common subsequence 最长公共子序列)所用例子基本是一样的,  
//都是测两串基因的相似程度,不同之处在于《导论》用LCS表示两基因的相似程度,LCS越长,相似度越大。  
//本题中用下面的核苷相近程度取值表表示两基因相似程度,各相应核苷对匹配值之和越高,相似程度自然越大。  
//首先回想LCS的解法,  
//设两基因串为an,bm  
//a[i],b[j]分别表示a串的第i个核苷,b串的第j个核苷  
//ax,by为an,bm的子串;  
//c[x][y]表示子串ax,by间最长子序列的长度  
//则c[n][m]表示串an,bm间最长子序列的长度  
//则有如下的状态转移方程:  
//c[i][j]=c[i-1][j-1]+1                            if i,j>0 a[i]=b[j]  
//c[i][j]=max(c[i][j-1],c[i-1][j])              if i,j>0 a[i]≠[j]  
//再思考该动规方程的边界条件:  
//for i=0 to n do c[i, 0] ← 0  
//for j=0 to n do c[0, j] ← 0  
//即每个子序列与长度为0的串的最长子序列的长度为0  
//此即为LCS的解法  
//  
//针对本题,对LCS的状态方程稍作修改,  
//设两基因串为an,bm  
//a[i],b[j]分别表示a串的第i个核苷  
//b串的第j个核苷  
//ax,by为an,bm的子串;  
//c[x][y]表示子串ax,by间最大相似程度值  
//则c[n][m]表示串an,bm间最大相似程度值  
//value(x,y)表示核苷x核苷y的相似程度值  
//'-'表示核苷为空  
//则有如下的状态转移方程:  
//c[i][j]=max(c[i-1][j-1]+value(a[i],b[j]),c[i][j-1]+value('-',b[j]),c[i-1][j]+value(a[i],'-'))  
//if i,j>0 a[i]≠[j]  
//再思考该动规方程的边界条件:  
//for i=0 to n do c[i][0] ← 0  
//for j=0 to n do c[0][j] ← 0  
//即每个子序列与空串之间的相似程度值的和为0  
//至此本题的思路已经清晰  
#include <iostream>  
#include <algorithm>  
using namespace std;  
int a[110],b[110],v[110][110];  
int r[5][5]={0,-3,-4,-2,-1,  
             -3,5,-1,-2,-1,  
             -4,-1,5,-3,-2,  
             -2,-2,-3,5,-2,  
             -1,-1,-2,-2,5};  
int change(char c){  
    switch (c){  
    case'A': return 1;  
    case'C': return 2;  
    case'G': return 3;  
    case'T': return 4;  
    }  
}  
int main(){  
    int n,st1len,st2len,i,j;  
    char ch;  
    cin>>n;  
    while(n--)  
    {  
        cin>>st1len;  
        for(i=1;i<=st1len;i++){  
            cin>>ch;  
            a[i]=change(ch);  
        }  
        cin>>st2len;  
        for(i=1;i<=st2len;i++){  
            cin>>ch;  
            b[i]=change(ch);  
        }  
        v[0][0]=0;  
        for(i=1;i<=st1len;i++) v[i][0]=r[a[i]][0]+v[i-1][0];  
        for(i=1;i<=st2len;i++) v[0][i]=r[0][b[i]]+v[0][i-1];  
        for(i=1;i<=st1len;i++)  
            for(j=1;j<=st2len;j++)  
                v[i][j]=max(v[i-1][j-1]+r[a[i]][b[j]],  
                max(v[i-1][j]+r[a[i]][0],v[i][j-1]+r[0][b[j]]));  
            cout<<v[st1len][st2len]<<endl;  
    }  
    return 0;  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日