首页 > 代码库 > HDU 1080 Human Gene Functions
HDU 1080 Human Gene Functions
最长公共子序列的变形
题目大意:给出两个基因序列,求这两个序列的最大相似度。
题目中的表格给出了两两脱氧核苷酸的相似度。
状态转移方程为:
dp[i][j] = max(dp[i-1][j]+Similarity(s1[i], ‘-‘),
dp[i][j-1]+Similarity(s2[j], ‘-‘),
dp[i-1][j-1]+Similarity(s1[i], s2[j]));
注意边界的初始化。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 char s1[105], s2[105]; 9 int dp[105][105];10 11 int table[5][5] = {12 5, -1, -2, -1, -3,13 -1, 5, -3, -2, -4,14 -2, -3, 5, -2, -2,15 -1, -2, -2, 5, -1,16 -3, -4, -2, -1, 017 }; 18 19 int max(int a, int b, int c)20 {21 return max(max(a, b), c);22 }23 24 int f(char c)25 {26 if(c == ‘A‘) return 0;27 if(c == ‘C‘) return 1;28 if(c == ‘G‘) return 2;29 if(c == ‘T‘) return 3;30 if(c == ‘-‘) return 4;31 }32 33 int Similarity(char c1, char c2)34 { return table[f(c1)][f(c2)]; }35 36 int main(void)37 {38 #ifdef LOCAL39 freopen("1080in.txt", "r", stdin);40 #endif41 42 int T;43 scanf("%d", &T);44 while(T--)45 {46 int len1, len2, i, j;47 dp[0][0] = 0;48 scanf("%d %s", &len1, s1+1);49 scanf("%d %s", &len2, s2+1);50 for(i = 1; i <= len1; ++i)51 dp[i][0] = dp[i-1][0] + Similarity(s1[i], ‘-‘);52 for(i = 1; i <= len2; ++i)53 dp[0][i] = dp[0][i-1] + Similarity(s2[i], ‘-‘);54 for(i = 1; i <= len1; ++i)55 for(j = 1; j <= len2; ++j)56 dp[i][j] = max(dp[i-1][j]+Similarity(s1[i], ‘-‘),57 dp[i][j-1]+Similarity(s2[j], ‘-‘),58 dp[i-1][j-1]+Similarity(s1[i], s2[j]));59 60 printf("%d\n", dp[len1][len2]);61 }62 return 0;63 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。