X星人的基因——题解

深碍√TFBOYSˉ_ 2023-01-19 13:59 186阅读 0赞

题目：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]  
样例输入：

8
    A B C D E A B C
    A C C D C B A E
    6
    A B C D E E
    A E D C B B
    0

样例输出：

思路：这题比较简单，就是先用动态规划求出最长公共子序列，再进行计算

Yes
    Yes

#include<iostream>
    #include<cmath>
    
    using namespace std;
    char a[10010],b[10010];
    int dp[1010][1010]={ 0};
    
    
    int main(){ 
    	int n;
    	while(cin>>n&&n){ 
    		for(int i=0;i<n+10;i++){      //初始化
    			for(int j=0;j<n+10;j++){ 
    				dp[i][j]=0;
    			}
    		}
    		for(int i=0;i<n;i++) cin>>a[i];       //输入
    		for(int i=0;i<n;i++) cin>>b[i];
    		
    		for(int i=0;i<n;i++){          //动态规划求出最长公共子序列
    			for(int j=0;j<n;j++){ 
    				if(a[i]==b[j]){ 
    					dp[i][j]=dp[i-1][j-1]+1;
    				} 
    				else { 
    					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    				}
    			}
    		}
    		
    		int num=dp[n-1][n-1];             //进行计算
    		double nu=(double)num/n;
    // cout<<num<<endl;
    		if(nu>0.5) cout<<"No"<<endl;       //判断输出结果
    		else cout<<"Yes"<<endl;
    	}
    	
    	
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]: /images/20221021/acfcb0d79b6e40af90f473c4f0aa4bcc.png

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关写一首名为《牧星人》的诗

好的，这是一首名为《牧星人》的诗: 牧星人，足迹清晰，山岗上的守护者。他与星星相知相识，把他们牵手长眠。他有着明亮的眼睛，把晚上的黑暗照亮。他用他的歌声唤醒，

刺骨的言语ヽ痛彻心扉/ 2024年03月25日 06:10/ 0 赞/ 86 阅读

相关【算法题解】37. Pow(x, n)

> 这是一道中等难度的题 > https://leetcode.cn/problems/powx-n/ 题目实现 p o w ( x , n ) pow(x

Myth丶恋晨/ 2024年03月16日 16:08/ 0 赞/ 41 阅读

相关【每日随笔】需要远离的人 ( 扫把星 : 穷人 / 不幸的人 / 固执的人 / 负能量消耗你的人 / 不懂感恩的人 )

文章目录一、远离穷人二、远离不幸的人三、远离固执的人四、远离负能量的人 / 消耗你的人五、远离不懂感恩的人拿出时间和

秒速五厘米/ 2023年10月14日 09:08/ 0 赞/ 47 阅读

相关 X星人的基因——题解

题目： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

深碍√TFBOYSˉ_/ 2023年01月19日 13:59/ 0 赞/ 187 阅读

相关 LeetCode题解：pow(x, n)

pow(x, n) 一、题目实现 pow(x, n) ，即计算 x 的 n 次幂函数。示例 1: 输入: 2.00000, 10 输出: 1

曾经终败给现在/ 2022年12月29日 09:28/ 0 赞/ 117 阅读

相关 X-factor Chains(POJ-3421)题解

文章目录题目描述输入格式输出格式输入输出算法分析解题标程错题总结

以你之姓@/ 2022年12月28日 07:29/ 0 赞/ 134 阅读

相关 LeetCode题解：x的平方根

x的平方根（easy） > 更好的阅读体验应该是： > > 1. 审题-思考 > 2. 答题 > 3. 整理-归纳一、题目 [LeetCode：69.x

客官°小女子只卖身不卖艺/ 2022年12月27日 08:49/ 0 赞/ 138 阅读

相关 bwa基因测序

bwa介绍 bwa 是一款将序列比对到参考基因组上的软件。常用算法是BWA-MEM。 BWA-MEM算法在比对长度为70-100bp的序列时，效果比BWA-backtr

淡淡的烟草味﹌/ 2022年12月02日 12:28/ 0 赞/ 342 阅读

相关相似基因

题目背景大家都知道，基因可以看作一个碱基对序列。它包含了44种核苷酸，简记作A,C,G,TA,C,G,T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物

今天药忘吃喽~/ 2022年03月07日 12:38/ 0 赞/ 270 阅读

相关【题解】X龙珠

明天好像要考链表今晚笔者来了解下。 [题目链接][Link 1] 解：对于这道题，由于前面要与后面重新连起来，于是我们考虑链表。我们先正常用链表维护关系。然后，我们

浅浅的花香味﹌/ 2021年11月27日 00:26/ 0 赞/ 317 阅读