Description

小A最近一直在找自己的爸爸,用什么办法呢,就是DNA比对。小A有一套自己的DNA序列比较方法,其最终目标是最
大化两个DNA序列的相似程度,具体步骤如下:1.给出两个DNA序列,第一个长度为n,第二个长度为m。2.在两个序
列的任意位置插入任意多的空格,使得两个字符串长度相同3.逐位进行匹配,如果两个序列相同位置上的字符都不
是空格,假设第一个是x,第二个是y,那么他们的相似程度由d(x,y)定义。对于两个序列中任意一段极长的长度为
k的连续空格,我们定义这段空格的相似程度为g(k)=-A-B(k-1)。那么最终两个序列的相似程度就是所有的d(x,y)
加上所有的极长空格段的相似程度之和。现在小A通过某种奥妙重重的方式得到了小B的DNA序列中的一段,他想请
你帮他算一下小A的DNA序列和小B的DNA序列的最大相似程度。
 

Input

输入第1行一个字符串,表示小A的DNA序列。
输入第2行一个字符串,表示小B的DNA序列。
接下来4行,每行4个整数,用空格隔开,表示d数组,
具体顺序如下所示。
d(A,A)d(A,T)d(A,G)d(A,C)
d(T,A)d(T,T)d(T,G)d(T,C)
d(G,A)d(G,T)d(G,G)d(G,C)
d(C,A)d(C,T)d(C,G)d(C,C)
最后一行两个用空格隔开的正整数A,B,意义如题中所述。
对于所有测试点
有0<B<A≤1000,-1000≤d(x,y)≤1000,d(x,y)=d(y,x),
序列只包含{A,T,G,C}四种字符。
N+M<=3000

Output

输出共一行,表示两个序列的最大相似程度

有一个特殊的性质:
一段长度为 $k$ 的连续空格的代价为 $-A-B(k-1)$.
可以看成第一个空格的代价为 $-A$, 其它空格代价为 $-B$.
那么我们就设状态 $f[i][j],g[i][j],h[i][j]$ 分别表示 $S$ 串前 $i$ 个与 $T$ 串前 $j$ 个达到长度相同,且最后一个字符分别为 字母/字母,字母/空格,空格/字母的最大相似度.
因为不可能出现空格/空格的情况,所以就不设这个状态了.
考虑转移:
$f[i][j]$ :

  • $\leftarrow f[i-1][j-1]+d(S[i],T[j])$.

$g[i][j]$:

  • $\leftarrow g[i-1][j]-A$.
  • $\leftarrow f[i-1][j]-B$.
  • $\leftarrow h[i-1][j]-A$

$h[i][j]$:

  • $\leftarrow g[i][j-1]-A$.
  • $\leftarrow f[i][j-1]-A$.
  • $\leftarrow h[i][j-1]-B$.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 3003
#define ll long long
#define setIO(s) freopen(s".in", "r" , stdin)
using namespace std;
char str[N];
int S[N], T[N], d[6][6], n, m;
ll f[N][N], g[N][N], h[N][N];
int id(char c)
{
if(c == 'A') return 1;
if(c == 'T') return 2;
if(c == 'G') return 3;
if(c == 'C') return 4;
}
int main()
{
// setIO("input");
int i , j, A, B;
scanf("%s", str + 1), n = strlen(str + 1);
for(i = 1; i <= n ; ++ i) S[i] = id(str[i]);
scanf("%s", str + 1), m = strlen(str + 1);
for(i = 1; i <= m ; ++ i) T[i] = id(str[i]);
for(i = 1; i <= 4 ; ++ i)
{
for(j = 1; j <= 4; ++j) scanf("%d", &d[i][j]);
}
scanf("%d%d", &A, &B);
memset(f, -63, sizeof(f)), memset(g, -63, sizeof(g)), memset(h, -63, sizeof(h));
g[1][0] = h[0][1] = - A, f[0][0] = 0;
for(i = 1; i <= n ; ++ i)
{
for(j = 1; j <= m ; ++ j)
{
f[i][j] = max(f[i - 1][j - 1], max(g[i - 1][j - 1], h[i - 1][j - 1])) + d[S[i]][T[j]];
g[i][j] = max(max(f[i - 1][j], h[i - 1][j]) - A, g[i - 1][j] - B);
h[i][j] = max(max(f[i][j - 1], g[i][j - 1]) - A, h[i][j - 1] - B);
}
}
printf("%lld\n", max(max(f[n][m], g[n][m]), h[n][m]));
return 0;
}

  

最新文章

  1. java中jqGrid时间戳格式转换
  2. iOS 应用内的系统复制粘贴菜单显示的语言非中文
  3. CEF3开发者系列之JS与C++交互之一
  4. Python学习笔记之字符串
  5. HighCharts入门
  6. core java 1~4(HelloWorld &amp; 标识符|关键字|数据类型 &amp; 表达式|流程控制 &amp; 数组)
  7. oninput和onpropertychange
  8. mysql 常用命令搜集
  9. python K-means工具包初解
  10. windows批处理實例
  11. 11.2、Libgdx的音频之音乐
  12. 新装的SSMS一打开就显示VS许可证过期,但VS又运行正常,解决方法。
  13. redis - Sentinel 和 cluster
  14. 面试linux运维一定会问到Shell脚本这24个问题
  15. electron入门
  16. codeforces 1037
  17. Java -- 内部类(二)
  18. 函数和常用模块【day06】:subprocess模块(十)
  19. c/s 给 服务器上传文件(c/s和b/s互传文件)
  20. TOP100summit:【分享实录-WalmartLabs】利用开源大数据技术构建WMX广告效益分析平台

热门文章

  1. JS实现网页选取截屏 保存+打印 功能(转)
  2. spring boot-7.日志系统
  3. [转帖]linux /proc目录下的文件为何无法用vi编辑保存
  4. 开发完成的springboot项目扩展 swagger
  5. java操作ElasticSearch(es)进行增删查改操作
  6. python简介与简单入门
  7. Mac 基于Anaconda的TensorFlow安装笔记
  8. 元素定位--firebug安装
  9. CentOS 7.6 下载和安装
  10. 点亮指路灯led