dp poj 1080 Human Gene Functions

题目链接：

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

题目大意：

给两个由A、C、T、G四个字符组成的字符串，可以在两串中加入-，使得两串长度相等。

每两个字符匹配时都有个值，求怎样安排使得总的值最大，两个-不能匹配。

解题思路：

这题转化一下就是一个裸的最长公共子串问题，只不过要求匹配时长度一样。

dp[i][j]表示第一串的第前i个字符和第二串的前j个字符匹配时，能达到的最大值。

初始化时注意dp[0][j]和dp[j][0]不能为零，为相应字符与-匹配时的总和。

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
#define Maxn 110
map<char,int>myp;
int mar[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,-INF}}; //存入值表
char sa1[Maxn],sa2[Maxn];
int a[Maxn],b[Maxn];
int dp[Maxn][Maxn];

int main()
{
   myp['A']=0,myp['C']=1,myp['G']=2,myp['T']=3,myp['-']=4; //将字符和表映射起来
   int t,len1,len2;

   scanf("%d",&t);
   while(t--)
   {
      scanf("%d%s",&len1,sa1+1);
      for(int i=1;i<=len1;i++)
         a[i]=myp[sa1[i]]; //转化成相应的代表数字
      scanf("%d%s",&len2,sa2+1);
      for(int i=1;i<=len2;i++)
         b[i]=myp[sa2[i]];

      memset(dp,-INF,sizeof(dp));
      dp[0][0]=0;
      for(int i=1;i<=len1;i++) //注意初始化时 是和-匹配
          dp[i][0]=dp[i-1][0]+mar[a[i]][4];
         // printf("i:%d j:%d %d
",i,0,dp[i][0]);
      for(int j=1;j<=len2;j++)
         dp[0][j]=dp[0][j-1]+mar[b[j]][4];
         //printf("i:%d j:%d %d
",0,j,dp[0][j]);
    //  putchar('
');
      for(int i=1;i<=len1;i++)
         for(int j=1;j<=len2;j++)
         {
            int Mx=dp[i][j];
            Mx=max(Mx,dp[i-1][j-1]+mar[a[i]][b[j]]); //i-j匹配
            Mx=max(Mx,max(dp[i-1][j]+mar[a[i]][4],dp[i][j-1]+mar[b[j]][4])); //(j和i-1,i和-)匹配 (i和j-1,-和j)匹配
            Mx=max(Mx,dp[i-1][j-1]+mar[a[i]][4]+mar[b[i]][4]); //两个都匹配-
            dp[i][j]=Mx;
            //printf("i:%d j:%d %d
",i,j,dp[i][j]);
         }
      printf("%d
",dp[len1][len2]);
   }
   return 0;
}

dp poj 1080 Human Gene Functions

相关推荐