首页 > 其他 > 详细

【洛谷习题】相似基因

时间:2018-09-08 00:35:17      阅读:270      评论:0      收藏:0      [点我收藏+]

题目链接:https://www.luogu.org/problemnew/show/P1140


语文很重要!!!如果题目意思都不理解,怎么可能写出正解?!两个序列都可以插空位!两个序列都可以插空位!两个序列都可以插空位!

其实如果写过最长公共子序列,这道题简直就是水题(考察阅读理解)。在这里放一波最长公共子序列,对于序列s1,s2,我们定义dp[i][j]表示考虑到s1的第i个元素,s2的第j个元素所能取到的最长公共子序列的长度,枚举i,j,若s1[i]=s2[j],则他们可以作为最长公共子序列的结尾,dp[i][j]=dp[i-1][j-1]+1;反之,s[i]和s[j]不可以作为最长公共子序列的结尾,dp[i][j]=max(dp[i][j-1],dp[i-1][j])。

本题同理,只不过字符的转换、dp数组初始化等细节需要处理好。

技术分享图片
 1 #include<cstdio>
 2 using namespace std;
 3 const int maxn=105;
 4 const int de[5][5]={
 5     {5,-1,-2,-1,-3},
 6     {-1,5,-3,-2,-4},
 7     {-2,-3,5,-2,-2},
 8     {-1,-2,-2,5,-1},
 9     {-3,-4,-2,-1,-0x3f3f3f3f}
10 };
11 int n1,n2,dp[maxn][maxn];
12 char s1[maxn],s2[maxn];
13 inline int max(int a,int b) {return a>b?a:b;}
14 int toint(char c) {
15     if(c==A) return 0;
16     else if(c==C) return 1;
17     else if(c==G) return 2;
18     else if(c==T) return 3;
19     else return 4;
20 }
21 int degree(char a,char b) {
22     return de[toint(a)][toint(b)];
23 }
24 int main() {
25     scanf("%d",&n1);scanf("%s",s1+1);
26     scanf("%d",&n2);scanf("%s",s2+1);
27     for(int i=1;i<=n1;++i) dp[i][0]=degree(s1[i],-)+dp[i-1][0];
28     for(int i=1;i<=n2;++i) dp[0][i]=degree(s2[i],-)+dp[0][i-1];
29     for(int i=1;i<=n1;++i)
30         for(int j=1;j<=n2;++j) {
31             dp[i][j]=dp[i-1][j-1]+degree(s1[i],s2[j]);
32             dp[i][j]=max(dp[i][j],dp[i-1][j]+degree(s1[i],-));
33             dp[i][j]=max(dp[i][j],dp[i][j-1]+degree(s2[j],-));
34         }
35     printf("%d",dp[n1][n2]);
36     return 0;
37 }
AC代码

 

【洛谷习题】相似基因

原文:https://www.cnblogs.com/Mr94Kevin/p/9607579.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!