動态規劃(DP)，Human Gene Functions

題目連結：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1027

http://poj.org/problem?id=1080

解題報告：

1、類似于LCS

2、gene[i][j]表示str1[i-1]和str2[j-1]的分值串沒有，則應該扣分

3、遞推公式

temp1=gene[i-1][j-1]+score[_map[str1[i-1]]][_map[str2[j-1]]];

temp2=gene[i-1][j]+score[_map[str1[i-1]]][4];

temp3=gene[i][j-1]+score[4][_map[str2[j-1]]];

gene[i][j]=max(temp1,max(temp2,temp3));

4、在初始化邊界條件時，認為一個字元串為空，則要扣分

#include <cstdio>
#include <algorithm>
#include <map>
#define NUM 105

using namespace std;

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}};

map<char,int> _map;

char str1[NUM],str2[NUM];
int len1,len2;

int gene[NUM][NUM];///gene[i][j]表示基因子串str1[i-1]和str2[j-1]的分值.

int main()
{
    _map['A']=0,_map['C']=1,_map['G']=2,_map['T']=3,_map['-']=4;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%s",&len1,str1);
        scanf("%d%s",&len2,str2);
        ///初始化邊界條件
        gene[0][0]=0;
        for(int i=1; i<=len1; i++)
            gene[i][0]=gene[i-1][0]+score[_map[str1[i-1]]][4];
        for(int i=1; i<=len2; i++)
            gene[0][i]=gene[0][i-1]+score[4][_map[str2[i-1]]];
        int m1,m2,m3;
        for(int i=1; i<=len1; i++)
        {
            for(int j=1; j<=len2; j++)
            {
                m1=gene[i-1][j]+score[_map[str1[i-1]]][4];///str1取i-1個字元，str2取'-';
                m2=gene[i][j-1]+score[4][_map[str2[j-1]]];///str1取'-',str2取j-1個字元;
                m3=gene[i-1][j-1]+score[_map[str1[i-1]]][_map[str2[j-1]]];///str1取i-1個字元，str2取j-1個字元
                gene[i][j]=max(m1,max(m2,m3));
            }
        }
        printf("%d\n",gene[len1][len2]);
    }
    return 0;
}      

轉載于:https://www.cnblogs.com/TreeDream/p/5260044.html