大家好，又见面了，我是全栈君。
匹配两个人相似度。
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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/115445.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
