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

题意:比较两个基因序列,测定它们的相似度,将两个基因排成直线,如果需要的话插入空格,使基因的长度相等,然后根据那个表格计算出相似度。

题解:

考虑f[i][j]:

①    s1取第i个,s2取第j个, f[i][j] = f[i-1][j-1]+value[m(s1[i])][m(s2[j])];

②    s1取第i个,s2用’-’, f[i][j] = f[i][j-1]+value[m(s1[i])][m(‘-’)];

③    s1用’-’,s2取第j个, f[i][j] = f[i-1][j]+value[m(‘-’)][m(s2[j])];

f[i][j] 为三者中最大者

考虑边界条件,即i或j为0的情况:

①                    当i=j=0时,根据f[1][1] = f[0][0]+value[m(s1[i])][m(s2[j])],有f[0][0] = 0;

②                    当i=0时,用f[0][j] = f[0][j-1]+ value[m(‘-’)][m(s2[j])]计算

③                    当j=0时,用f[i][0] = f[i-1][0]+ value[m(s1[i])][m(‘-’)]计算

 #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; int mmax(int a,int b,int c)
{
if(a>=b&&a>=c)
return a;
if(b>=a&&b>=c)
return b;
if(c>=a&&c>=b)
return c;
}
int f[][]={,-,-,-,-,
-,,-,-,-,
-,-,,-,-,
-,-,-,,-,
-,-,-,-,
}; int tran(char ch)
{
switch(ch)
{
case 'A':return ; break;
case 'C':return ; break;
case 'G':return ; break;
case 'T':return ; break;
case '-':return ;
}
}
int d[][];
int main()
{
int t,i,j,m,n;
char a[],b[];
cin>>t;
while(t--)
{
memset(d,,sizeof(d));
cin>>m; getchar();
cin>>a;
cin>>n; getchar();
cin>>b;
d[][]=;
for(j=; j<=n; j++)
d[][j]=f[tran('-')][tran(b[j-])]+d[][j-];//这里刚开始求成了最大的,其实应该是每一个的- 与
//每一个的字符串匹配后的值, 而后面循环里的每一个d【i】[j]实际都有相同的字符,不足的是- 补全的。 for(i=; i<=m; i++)
d[i][]=f[tran(a[i-])][tran('-')]+d[i-][];
for(i=; i<=m; i++)
for(j=; j<=n; j++)
{
d[i][j]=mmax(f[tran(a[i-])][tran(b[j-])]+d[i-][j-],f[tran('-')][tran(b[j-])]+d[i][j-],
f[tran(a[i-])][tran('-')]+d[i-][j]);// 因为输入的原因,d 和 a. b 相差 一
}
cout<<d[m][n]<<endl;
}
return ;
}

最新文章

  1. CSS3自动添加省略号
  2. 使用jsvc启动tomcat
  3. RESTful HTTP的实践
  4. Spring JdbcTemplate小结
  5. E题 - A+B for Input-Output Practice (IV)
  6. PHP多线程的实现(PHP多线程类)
  7. ASP.NET - 使用MqSql数据库
  8. EF如何操作内存中的数据和加载外键数据:延迟加载、贪婪加载、显示加载
  9. 关于JVM的垃圾回收(GC) 这可能是你想了解的
  10. 题解 P3871 【[TJOI2010]中位数】
  11. 【CodeForces 730H】Car Repair Shop
  12. QQ网页弹窗
  13. 电梯间的谈话:3分钟快速回答CEO的问题
  14. System.Web.Optimization 找不到引用,教你如何解决?
  15. HDU 1535 Invitation Cards(逆向思维+邻接表+优先队列的Dijkstra算法)
  16. nginx中的break与last指令区别
  17. Codeforces Round #360 (Div. 1) D. Dividing Kingdom II 暴力并查集
  18. 安装 Win10 &amp; Ubuntu 16.04 双系统以及 Ubuntu 配置深度学习环境记录
  19. 关于JS里的函数作用域链的总结
  20. bat遍历当前目录下的文件,批量重命名

热门文章

  1. 我的LESS编译方案
  2. Python 5 —— OOP
  3. CGFloat Float 互转
  4. 2.C#自定义Attribute
  5. 静态类和静态类成员(C# 编程指南)
  6. awesome-very-deep-learning
  7. [BZOJ 1036] [ZJOI2008] 树的统计Count 【Link Cut Tree】
  8. C#获取磁盘列表与信息
  9. canvas阴影
  10. 远程连接MySQL 不允许
  11. TD-SCDMA风雨20年:中国3G标准的由来以及国家通信战略
  12. [LeetCode299]Bulls and Cows
  13. 【xcode插件介绍】Alcatraz ----The package manager for Xcode
  14. hdu5556 Land of Farms
  15. Web Application Vulnerablities
  16. Difference between ulimit, lsof, cat /proc/sys/fs/file-max
  17. vue axios使用form-data的形式提交数据的问题
  18. [蓝桥杯]PREV-7.历届试题_连号区间数
  19. 分组查询以及having使用
  20. linux日志管理