洛谷P1140相似基因

【题目链接】

洛谷 P1140 相似基因

【题目考点】 1. 线性动规：求最长公共子序列 【解题思路】

将ACGT四种碱基，以及无碱基对应五个编号：A-0, C-1, G-2, T-3, 无-4 先设二维数组p保存碱基之间的相似度，p[i][j]表示编号为i的碱基和编号为j的碱基之间的相似度。 特殊地，无碱基和无碱基的相似度p[4][4]在代码中不会用到，设为0就行。

给定两个有ACGT构成的基因序列，也就是由整数0~3构成的整数序列，在这两个序列中取出两个子序列，可以在两个子序列中任意位置插入任意数量的4（也就是无-)，得到两个等长的序列。这两个等长序列对应位置的数字构成很多数对。 这两个序列的相似度为数对序列中每个数对的相似度的加和。 求两序列的取出两子序列能得到的最大的相似度。

该题形式和最长公共子序列问题相似，可以用与之相似的方法定义状态，分析状态转移方程。

1. 状态定义

给定两个整数序列分别为a、b，长度分别为an、bn。

阶段：a的前i个数字，b的前j个数字决策：确定一个数对 一个序列中的一个数字和另一序列中的一个数字对应，可以构成一个数对。 一个序列中的一个数字不与另一序列中的个数字对应，那么也就是和数字4对应，也可以构成数对。策略：数对序列策略集合：a的前i个数字，b的前j个数字所能构成的所有数对序列条件：每个数对的相似度加和最大统计量：相似度

状态定义： dp[i][j]：a的前i个数字与b的前j个数字所能构成的所有数对序列中，相似度加和最大的序列的相似度。 初始状态 dp[0][0] = 0：a的前0个数字与b的前0个数字所能构成的所有数对序列的相似度一定为0。 dp[i][0]：a的前i个数字与b的前0个数字所能构成的所有数对的相似度，就是a的前i个数字每个数字都与数字4配对。 a的前i个数字都与4配对的相似度，就是a的前i-1个数字都与4配对的相似度，加上第i个数字与4配对的相似度。 满足递推式dp[i][0] = dp[i-1][0]+p[a[i]][4] dp[0][j]：a的前0个数字与b的前j个数字所能构成的所有数对的相似度，就是b的前j个数字每个数字都与数字4配对。 b的前j个数字都与4配对的相似度，就是b的前j-1个数字都与4配对的相似度，加上第j个数字与4配对的相似度。 满足递推式dp[0][j] = dp[0][j-1]+p[4][b[j]]

状态转移方程 策略集合：a的前i个数字，b的前j个数字所能构成的所有数对序列分割策略集合：根据如何构造最后一个数对分割策略集合 如果最后一个数对是a的第i个数字和“无”构成的，也就是(a[i],4)，那么a的前i个数字与b的前j个数字的最大相似度，就是a的前i-1个数字与b的前j个数字的最大相似度，再加上数对(a[i], 4)的相似度，即dp[i-1][j]+p[a[i]][4]如果最后一个数对是“无”和b的第j个数字构成的，即(4, b[j])那么a的前i个数字与b的前j个数字的最大相似度，就是a的前i个数字与b的前j-1个数字的最大相似度，再加上数对(4, b[j])的相似度，即dp[i][j-1]+p[4][b[j]]如果最后一个数对是a的第i个数字和b的第j个数字构成的，即(a[i], b[j])那么a的前i个数字与b的前j个数字的最大相似度，就是a的前i-1个数字与b的前j-1个数字的最大相似度，再加上数对(a[i], b[j])的相似度，即dp[i-1][j-1]+p[a[i]][b[j]]以上三种情况取最大值，即为dp[i][j]的值。

最后，序列a、b（长为an、bn）的最大相似度为dp[an][bn]。

【题解代码】 解法1：线性动规 #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; #define N 105 int p[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}};//p[i][j]：下标i对应字符与下标j对应字符的相似度 特殊地，空变为空相似度应该为0。 int a[N], b[N], an, bn, dp[N][N];//dp[i][j]：a的前i个字符与b的前j个字符的最大相似度，a的前i个字符与b的前j个字符的所有对应方案中，相似度最高的方案的相似度 int toNum(char c)//获取字符c对应的下标 { switch(c) { case 'A': return 0; case 'C': return 1; case 'G': return 2; case 'T': return 3; } } int main() { char c; cin >> an; for(int i = 1; i <= an; ++i) { cin >> c; a[i] = toNum(c); } cin >> bn; for(int i = 1; i <= bn; ++i) { cin >> c; b[i] = toNum(c); } for(int i = 1; i <= an; ++i) dp[i][0] = dp[i-1][0]+p[a[i]][4]; for(int j = 1; j <= bn; ++j) dp[0][j] = dp[0][j-1]+p[4][b[j]]; for(int i = 1; i <= an; ++i) for(int j = 1; j <= bn; ++j) dp[i][j] = max(dp[i-1][j]+p[a[i]][4], max(dp[i][j-1]+p[4][b[j]], dp[i-1][j-1]+p[a[i]][b[j]])); cout << dp[an][bn]; return 0; }