ZOJ 1027 Human Gene Functions(DP)

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1027

设f[i][j]为基因1的前 i 个核苷酸与基因2的前 j 个核苷酸匹配所得的最高分数。

则 f[i][j]= max {

f[i-1][j-1]+ score[i][j], //基因1的前 i-1 个核苷酸与基因2的前 j-1 个核苷酸匹配，score[i][j]为核苷酸 i 与核苷酸 j 匹配的得分

f[i-1][j] + score[i][], //基因1的前 i-1 个核苷酸与基因2的前 j 个核苷酸匹配，score[i][]为核苷酸 i 与空格匹配的得分

f[i][j-1] + score[][j] //基因1的前 i 个核苷酸与基因2的前 j-1 个核苷酸匹配，score[][j]为空格与核苷酸 j 匹配的得分

}

初始条件如下：

f[0][0]=0;

f[i][0]= score[1][]+score[2][]+score[3][]+...+score[i][] ;

f[i][0]= score[][1]+score[][2]+score[][3]+...+score[][i] ;

代码如下：

#include<iostream>
using namespace std;

int max(int x,int y)
{
    return x>y? x:y;
}

int f[101][101];

int main()
{
    int score[5][5]={
        {5,-1,-2,-1,-3},
        {-1,5,-3,-2,-4},
        {-2,-3,5,-2,-2},
        {-1,-2,-2,5,-1},
        {-3,-4,-2,-1,0}
    };
    int N;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        int len1,len2,gen1[101],gen2[101];
        char c;
        cin>>len1;
        int tmp=0;
        for(int j=1;j<=len1;j++)
        {
            cin>>c;
            if(c=='A')
                gen1[j]=0;
            else if(c=='C')
                gen1[j]=1;
            else if(c=='G')
                gen1[j]=2;
            else if(c=='T')
                gen1[j]=3;
            tmp+=score[gen1[j]][4];
            f[j][0]=tmp;
        }
        cin>>len2;
        tmp=0;
        for(int j=1;j<=len2;j++)
        {
            cin>>c;
            if(c=='A')
                gen2[j]=0;
            else if(c=='C')
                gen2[j]=1;
            else if(c=='G')
                gen2[j]=2;
            else if(c=='T')
                gen2[j]=3;
            tmp+=score[4][gen2[j]];
            f[0][j]=tmp;
        }
        //////////////////////////////////////////DP COMPUT
        f[0][0]=0;
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                f[i][j]=f[i-1][j-1]+score[gen1[i]][gen2[j]];
                f[i][j]=max( f[i-1][j]+score[gen1[i]][4],f[i][j] );
                f[i][j]=max( f[i][j-1]+score[4][gen2[j]],f[i][j] );
                    
            }
        }
        cout<<f[len1][len2]<<endl;

    }
    return 0;
}