匹配两个人相似度。A，G，C。T。每两个都会有一个相应的值，给出两串基因。长度能够不一样，能够在基因中间加_使两串长度一样。然后有一个相应值。求最大相应值。

先做出相应的表

DP方程：

x=dp[i-1][j-1]+hash[str_a[i-1]][str_b[j-1]];

y=dp[i-1][j]+hash[str_a[i-1]]['-'];

z=dp[i][j-1]+hash[str_b[j-1]]['-'];

p[i][j]=Max(x,y,z);

#include "stdio.h"

#include "string.h"

int Max(int a,int b,int c)

{

int x;

x=a;

if (b>x) x=b;

if (c>x) x=c;

return x;

}

int main()

{

int Case,len_a,len_b,x,y,z,i,j;

int dp[110][110],hash[210][210];

char str_a[110],str_b[110];

hash['A']['A']=hash['C']['C']=hash['T']['T']=hash['G']['G']=5;

hash['A']['C']=hash['C']['A']=hash['A']['T']=hash['T']['A']=hash['-']['T']=hash['T']['-']=-1;

hash['A']['G']=hash['G']['A']=hash['C']['T']=hash['T']['C']=hash['G']['T']=hash['T']['G']=hash['-']['G']=hash['G']['-']=-2;

hash['A']['-']=hash['-']['A']=hash['C']['G']=hash['G']['C']=-3;

hash['C']['-']=hash['-']['C']=-4;

scanf("%d",&Case);

while (Case--)

{

scanf("%d%s%d%s",&len_a,str_a,&len_b,str_b);

// memset(dp,0,sizeof(dp));

dp[0][0]=0;

for (i=1;i<=len_a;i++)

dp[i][0]=dp[i-1][0]+hash['-'][str_a[i-1]];

for (i=1;i<=len_b;i++)

dp[0][i]=dp[0][i-1]+hash['-'][str_b[i-1]];

for (i=1;i<=len_a;i++)

for (j=1;j<=len_b;j++)

{

x=dp[i-1][j-1]+hash[str_a[i-1]][str_b[j-1]];

y=dp[i-1][j]+hash[str_a[i-1]]['-'];

z=dp[i][j-1]+hash[str_b[j-1]]['-'];

dp[i][j]=Max(x,y,z);

}

printf("%d\n",dp[len_a][len_b]);

}

return 0;

}

查看原文