hdu 1080 Human Gene Functions --- LCS问题变形

题意：

两个字符串 包含 A T C G - 五种字符 两两之间对应一个数值

给两个字符串 可以向其中添加一定的-  要使两字符串对应分值和最大 求该值

很好的LCS变形。。

dp[i][j]表示s1前i位和s2前j位所能构成的最大值

那么 如何递推呢 根据题意

比较到 i j 位时 此时可以有三种情况

1、s1[i] 对应 -

2、s2[j] 对应 -

3、s1[i] 对应 s2[j]

注意一下字符对应到分值的细节 就是个简单的问题了

#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;


map<char,int> mp;
int dp[105][105];//dp[i][j]表示s1前i位和s2前j位所能构成的最大值
char s1[105],s2[105];

int max3(int a,int b,int c)
{
    if(a>b)
    {
        if(a>c) return a;
        return c;
    }
    else
    {
        if(b>c) return b;
        return c;
    }
}

int main()
{
    int l1,l2,t,i,j,tmp1,tmp2,tmp3;
    mp[‘A‘]=0;
    mp[‘C‘]=1;
    mp[‘G‘]=2;
    mp[‘T‘]=3;
    mp[‘-‘]=4;
    int sco[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}};

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%s%d%s",&l1,s1,&l2,s2);
        //初始化
        dp[0][0]=0;
        for(i=1;i<=l1;i++)
            dp[i][0]=dp[i-1][0]+sco[mp[s1[i-1]]][4];
        for(i=1;i<=l2;i++)
            dp[0][i]=dp[0][i-1]+sco[4][mp[s2[i-1]]];
        
        for(i=1;i<=l1;i++)
        {
            for(j=1;j<=l2;j++)
            {
                tmp1=dp[i-1][j]+sco[mp[s1[i-1]]][4];
                tmp2=dp[i][j-1]+sco[4][mp[s2[j-1]]];
                tmp3=dp[i-1][j-1]+sco[mp[s1[i-1]]][mp[s2[j-1]]];
                dp[i][j]=max3(tmp1,tmp2,tmp3);
            }
        }
        printf("%d\n",dp[l1][l2]);
    }
    return 0;
}

hdu 1080 Human Gene Functions --- LCS问题变形

原文：http://blog.csdn.net/u011032846/article/details/19301111