poj 1080 Human Gene Functions (最长公共子序列变形)

题意：有两个代表基因序列的字符串s1和s2，在两个基因序列中通过添加"-"来使得两个序列等长；其中每对基因匹配时会形成题中图片所示匹配值，求所能得到的总的最大匹配值。

题解：这题运用dp的解法是借用了求最长公共子序列的方法，，定义dp[i][j]代表s1以第i位结尾的串和s2以第j位结尾的串匹配时所能得到的最大匹配值；那么状态转移方程为：dp[i][j]=max( dp[i-1][j-1]+s1[i]和s2[j]的匹配值 , dp[i-1][j]+s1[i]和'-'的匹配值 , dp[i][j-1]+s2[j]和'-'的匹配值 ); 另外要初始化dp[0][0]=0以及dp[i][0]和dp[0][j]的值。

AC代码：

 1 /**
 2 *@author Wixson
 3 */
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include <set>
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 const int inf=0x3f3f3f3f;
16 const double PI=acos(-1.0);
17 const double EPS=1e-10;
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int,int> P;
21 
22 char s1[205],s2[205];
23 int len1,len2;
24 int dp[205][205];
25 int m[5][5] = {{5,-1,-2,-1,-3},
26                 {-1,5,-3,-2,-4},
27                 {-2,-3,5,-2,-2},
28                 {-1,-2,-2,5,-1},
29                 {-3,-4,-2,-1,0}};
30 int d[500];
31 int max(int a,int b,int c)
32 {
33     return max(a,max(b,c));
34 }
35 int main()
36 {
37     //freopen("input.txt","r",stdin);
38     d['A']=0,d['C']=1,d['G']=2,d['T']=3,d['-']=4;
39     int T;
40     scanf("%d",&T);
41     while(T--)
42     {
43         scanf("%d%s",&len1,s1+1);
44         scanf("%d%s",&len2,s2+1);
45         //
46         dp[0][0]=0;
47         for(int i=1;i<=len1;i++) dp[i][0]=dp[i-1][0]+m[d[s1[i]]][d['-']];
48         for(int i=1;i<=len2;i++) dp[0][i]=dp[0][i-1]+m[d['-']][d[s2[i]]];
49         //
50         for(int i=1;i<=len1;i++)
51         {
52             for(int j=1;j<=len2;j++)
53             {
54                 dp[i][j]=max(dp[i-1][j-1]+m[d[s1[i]]][d[s2[j]]],dp[i-1][j]+m[d[s1[i]]][d['-']],dp[i][j-1]+m[d['-']][d[s2[j]]]);
55             }
56         }
57         //
58         printf("%d\n",dp[len1][len2]);
59     }
60     return 0;
61 }

poj 1080 Human Gene Functions (最长公共子序列变形)

相关

DP决策优化小结

dp专题练习

腾讯云搭建个人博客wordpress

dp多维状态的优化

CS5265完全替代兼容龙迅LT8711|Type-C/DP1.2 to HDMI2.0方案芯片|CS5265兼容TYPEC手机

Java高并发，ThreadPoolExecutor线程池技术

sqlserver with(NOLOCK) 或 with(READPAST）

单调队列优化DP历险记

CS5262设计DP转HDMI 4K60HZ +VGA 1080P方案芯片

「NOI2020」命运（树形DP+线段树合并）

线程池ThreadPool知识碎片和使用经验速记

阿里面试官常问的TCP和UDP，你真的弄懂了吗？

标签