首页 > 代码库 > POJ #1080 - Human Gene Functions
POJ #1080 - Human Gene Functions
A classic 2D DP problem. A disguise of LCS - actually not very hard to decode: it is about 2 sequences‘ matching, though with a weight value of each match.
The point of this problem: how to decode problem statement and how to distill the actuall model behind. Coding is not very hard, but my 80% debug time is spent on a stupid detail: in the 2 level for loop, indices start from 1, but char index of each string should be i - 1, j - 1.
Main reference: http://blog.csdn.net/xiaoxiaoluo/article/details/7366537
The AC code:
// 1080// http://blog.csdn.net/xiaoxiaoluo/article/details/7366537/* * Q1: What is the target value? Similarity Val * Q2: What are the Variables? indices of two strings * So, dp[i][j] = val * in which i is the index of 1st string, j is of the 2nd, and value is similarity * * The key is recurrence relations: * Eq1: s0[i] isChar, s1[j] isChar dp[i][j] = dp[i-1][j-1] + score[s0[i]][s1[j]] Eq2: s0[i] isChar, s1[j] is ‘-‘ dp[i][j] = dp[i][j-1] + score[‘-‘][s1[j]] Eq3: s0[i] is ‘-‘, s1[j] isChar dp[i][j] = dp[i-1][j] + score[s0[i]][‘-‘] The above eqs are to simulate LCS eqs. ‘-‘ is artificially put to match strings */#include <stdio.h>#define MAX_LEN 100int score[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 }};int Inx(char c){ switch (c) { case ‘A‘: return 0; case ‘C‘: return 1; case ‘G‘: return 2; case ‘T‘: return 3; case ‘-‘: return 4; }}int max2(int a, int b){ return (a > b) ? (a) : (b);}int calc(int len0, char in0[MAX_LEN], int len1, char in1[MAX_LEN]){ int dp[MAX_LEN + 1][MAX_LEN + 1]; // Init dp[0][0] = 0; for (int i = 1; i <= len0; i ++) { dp[i][0] = dp[i - 1][0] + score[Inx(in0[i-1])][Inx(‘-‘)]; // eq2 } for (int j = 1; j <= len1; j++) { dp[0][j] = dp[0][j - 1] + score[Inx(‘-‘)][Inx(in1[j-1])]; // eq1 } // Go for (int i = 1; i <= len0; i ++) for (int j = 1; j <= len1; j ++) { int val0 = dp[i - 1][j - 1] + score[Inx(in0[i-1])][Inx(in1[j-1])]; int val1 = dp[i][j - 1] + score[Inx(‘-‘)][Inx(in1[j-1])]; int val2 = dp[i - 1][j] + score[Inx(in0[i-1])][Inx(‘-‘)]; dp[i][j] = max2(val0, max2(val1, val2)); } return dp[len0][len1];}int main(){ int n; scanf("%d", &n); while (n--) { int len[2] = { 0 }; char in0[MAX_LEN] = { 0 }; char in1[MAX_LEN] = { 0 }; scanf("%d", len); scanf("%s", in0); scanf("%d", len + 1); scanf("%s", in1); int ret = calc(len[0], in0, len[1], in1); printf("%d\n", ret); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。