大家好,又见面了,我是全栈君。
匹配两个人相似度。
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账号...