POJ 1080 Human Gene Functions(DP:LCS)-白红宇

POJ 1080 Human Gene Functions(DP:LCS)

阅读量：5789 次

发布时间：2019-06-18

本文共 1580 字，大约阅读时间需要 5 分钟。

题意：

人类基因有两条，现在给出两个字符串，有长有短，可以在字符串中插入空格，要求对照表使两个字符串得出的相似值最大。

要点：

是LCS的变形，用dp[i][j]存储第一个字符串前i个字符与第二个字符串前j个字符的相似值的最大值，可以这么理解，要么就两个字符串都不加空格，要么其中一个加一个不加。这样可以写出状态转移方程为：dp[i][j]=max(dp[i - 1][j - 1] + matrix[val[a[i]]][val[b[j]]]，dp[i - 1][j] + matrix[val[a[i]]][val['-']]， dp[i][j - 1] + matrix[val['-']][val[b[j]]])。这题的边界条件不太一样，除了dp[0][0]=0以外，其他的：dp[0][i] = dp[0][i-1] + matrix[val['-']][val[b[i]]]，dp[i][0] = dp[i-1][0] + matrix[val['-'] ][val[a[i]]]。可以这么理解，为0就是空格，也是有相似值的。

15656931

Accepted

272K

16MS

1032B

2016-07-03 16:39:17

#include
    
     #include
     
      #include
      
       #include
       
        #include
        using namespace std;int dp[200][200];int matrix[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 } };map
         
           val;int main(){ int i, j, t,len1,len2; val['A'] = 0; val['C'] = 1; val['G'] = 2; val['T'] = 3; val['-'] = 4; char a[200], b[200]; scanf("%d", &t); while (t--) { scanf("%d%s", &len1, a + 1); scanf("%d%s", &len2, b + 1); dp[0][0] = 0; for (i = 1; i <= len1; i++) dp[i][0] = dp[i-1][0] + matrix[val['-'] ][val[a[i]]]; for (i = 1; i <= len2; i++) dp[0][i] = dp[0][i-1] + matrix[val['-']][val[b[i]]]; for(i=1;i<=len1;i++) for (j = 1; j <= len2; j++) { dp[i][j] = dp[i - 1][j - 1] + matrix[val[a[i]]][val[b[j]]]; dp[i][j] = max(dp[i][j], dp[i - 1][j] + matrix[val[a[i]]][val['-']]); dp[i][j] = max(dp[i][j], dp[i][j - 1] + matrix[val['-']][val[b[j]]]); } printf("%d\n", dp[len1][len2]); } return 0;}

转载于:https://www.cnblogs.com/seasonal/p/10343719.html

你可能感兴趣的文章