1027:给出两串基因判断相似度。不同的匹配关系由下表分值决定
两串基因串长度不一定相等。用-补齐,其中-和-不能匹配。求最大匹配分值。
如
A G T G A T G
- G T T A - G
最大分值:(-3)+5+5+(-2)+5+(-1) +5=14
思路:最优问题,动态规划。关键是找出递推关系,避免重复计算。
出入串A,B 长度分别为i,j 倒着考虑
引入二维数组 opt[i][j] 每一项代表长度i的A串和长度j的B串的最大匹配分值。
最后一位可能的匹配方式有三种,总想法是新最优=最后的匹配分+之前的最优
A为- B为字母 opt[i][j]=lastscore + opt[i][j-1]
A为字母 B为- opt[i][j]=lastscore + opt[i-1][j]
A为字母 B为字母 opt[i][j]=lastscore + opt[i-1][j-1]
取三者的最大值即可计算。
i=0时说明A串全为- 可以算出不同B串的得分。
j=0时说明B串全为- 可以算出不同A串的得分。
opt[0][0]=0。 这些作为初始值。
从opt[0][0]开始,逐步计算扩展,得到opt[i][j]。
#include<stdio.h>
#include<map>
#include<iostream>
using namespace std;
#define MaxN 101
char str1[MaxN],str2[MaxN];
map<char,int> m;
int opt[MaxN][MaxN];
int main()
{
m['A']=0;
m['C']=1;
m['G']=2;
m['T']=3;
m['-']=4;
int score[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}};
int len1;
int len2;
int N;
cin>>N;
for(int k=0;k<N;k++)
{
cin>>len1;
cin>>str1;
cin>>len2;
cin>>str2;
opt[0][0]=0;
for(int i=1;i<=len1;i++)
opt[i][0] = opt[i-1][0] + score[m[str1[i-1]]][4];
for(int i=1;i<len2;i++)
opt[0][i] = opt[0][i-1] + score[4][m[str2[i-1]]];
int m1,m2,m3;
for(int i=1;i<=len1;i++)
for(int j=1;j<=len2;j++)
{
m1=opt[i-1][j]+score[m[str1[i-1]]][4];
m2=opt[i][j-1]+score[4][m[str2[j-1]]];
m3=opt[i-1][j-1]+score[m[str1[i-1]]][m[str2[j-1]]];
int max=m1;
if(m2>max)
max=m2;
if(m3>max)
max=m3;
opt[i][j]=max;
}
cout<<opt[len1][len2]<<endl;
}
}
- 大小: 2.9 KB
分享到:
相关推荐
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
zoj1027解题指南和代码,还不错,是学校培训给的。
zoj 1140-zju 2433 简单题的部分答案 都是可以正确通过的,简洁易懂
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载
zoj 3590 -3+1.md
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj 3212 K-Nice.md
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 2561 Order-Preserving Codes.md
acm中zoj1002的可运行C++程序
NULL 博文链接:https://weitch.iteye.com/blog/1006972
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码