1. 题目分析

问题描述

我们需要比较两个基因序列的相似度，通过在适当位置插入空格（"-"）使它们长度相同，并根据给定的评分矩阵计算最优比对得分。目标是找到使总得分最高的比对方式。

输入输出

• 输入：
  • 测试用例数量$T$
  • 每个测试用例包含两行，每行一个基因序列及其长度
• 输出：
  • 每个测试用例的最优比对得分

关键点

• 基因序列由字符A、C、G、T组成
• 可以插入空格（"-"）进行对齐
• 根据评分矩阵计算比对得分
• 需要找到最大得分的比对方式

2. 解题思路

动态规划方法

使用动态规划来解决序列比对问题：

1. 状态定义：

• $f[i][j]$表示序列$a$的前$i$个字符和序列$b$的前$j$个字符的最优比对得分

2. 状态转移：

• 如果$a[i]$与$b[j]$匹配：$$f[i][j] = f[i-1][j-1] + score(a[i],b[j])$$
• 如果在$a$中插入空格：$$f[i][j] = f[i][j-1] + score('-',b[j])$$
• 如果在$b$中插入空格：$$f[i][j] = f[i-1][j] + score(a[i],'-')$$

3. 初始条件：

• $f[0][0] = 0$
• $f[i][0] = f[i-1][0] + score(a[i],'-')$
• $f[0][j] = f[0][j-1] + score('-',b[j])$

4.最终结果：

• $f[n][m]$即为最优比对得分

3. 复杂度分析

• 时间复杂度：$O(n \times m)$，其中$n$和$m$是两个序列的长度
• 空间复杂度：$O(n \times m)$，可以使用滚动数组优化到$O(min(n,m))$

4. 代码实现

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 110;

int dx[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, -9};

char a[N], b[N];
int n, m;
int f[N][N];

int getnum(char c)
{
	if(c == 'A') return 0;
	if(c == 'C') return 1;
	if(c == 'G') return 2;
	if(c == 'T') return 3;
}

int main()
{
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	while(t --)
	{
		cin >> n >> a + 1 >> m >> b + 1;
		
		f[0][0] = 0;
		for(int i = 1; i <= n; i ++ ) f[i][0] = f[i - 1][0] + dx[getnum(a[i])][4];
		for(int j = 1; j <= m; j ++ ) f[0][j] = f[0][j - 1] + dx[4][getnum(b[j])];
		
		for(int i = 1; i <= n; i ++ )
			for(int j = 1; j <= m; j ++ )
			{
				int x = getnum(a[i]), y = getnum(b[j]);
				f[i][j] = max(f[i - 1][j - 1] + dx[x][y], max(f[i - 1][j] + dx[x][4], f[i][j - 1] + dx[4][y]));
			}
			
		cout << f[n][m] << endl;
	}
}