动态规划入门（二维一边推4：相似基因）

ID: 700

传统题

1000ms

128MiB

难度: (无)

上传者:

题目描述

匹配两个由 $\texttt{A}$ ， $\texttt{C}$ ， $\texttt{G}$ ， $\texttt{T}$ 组成的基因，计算它们的相似度。相似度的计算方法如下：

$/$	$\texttt{A}$	$\texttt{C}$	$\texttt{G}$	$\texttt{T}$	$-$
$\texttt{A}$	$5$	$-1$	$-2$	$-1$	$-3$
$\texttt{C}$	$-1$	$5$	$-3$	$-2$	$-4$
$\texttt{G}$	$-2$	$-3$	$5$	$-2$	$-2$
$\texttt{T}$	$-1$	$-2$	$-2$	$5$	$-1$
$-$	$-3$	$-4$	$-2$	$-1$	$0$

例如 $\texttt{AGTGATG}$ 和 $\texttt{GTTAG}$ ，将它们的碱基互相对应。当然，中间可以加入一些空碱基 $\texttt{-}$ ，所以对应方法不唯一。

例如：

$\texttt{AGTGAT-G}$
$\texttt{-GT--TAG}$

相似度就是 $(-3)+5+5+(-2)+(-3)+5+(-3)+5=9$ 。

例如又有：

$\texttt{AGTGATG}$
$\texttt{-GTT-AG}$

相似度为： $(-3)+ 5+5+(-2)+5+(-1)+5=14$ 。

要求相似度最大。

共两行。每行首先是一个整数，表示基因的长度；隔一个空格后是一个基因序列，序列中只含 $\texttt{A}$ ， $\texttt{C}$ ， $\texttt{G}$ ， $\texttt{T}$ 四个字母。

仅一行，即输入基因的相似度。

7 AGTGATG
5 GTTAG

$1\le$ 序列的长度 $\le 100$