热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDU1503:高级水果的最长公共子序列路径分析

题目描述:21世纪水果公司专注于开发新型水果品种。本研究通过高级水果的最长公共子序列路径分析,探讨了不同水果品种之间的遗传关系和进化路径,为新品种的培育提供了科学依据。该方法不仅提高了品种鉴定的准确性,还为遗传多样性研究提供了新的视角。
Problem Description
The company "21st Century Fruits" has specialized in creating new sorts of fruits by transferring genes from one fruit into the genome of another one. Most times this method doesn't work, but sometimes, in very rare cases, a new fruit emerges that tastes like a mixture between both of them. 
A big topic of discussion inside the company is "How should the new creations be called?" A mixture between an apple and a pear could be called an apple-pear, of course, but this doesn't sound very interesting. The boss finally decides to use the shortest string that contains both names of the original fruits as sub-strings as the new name. For instance, "applear" contains "apple" and "pear" (APPLEar and apPlEAR), and there is no shorter string that has the same property. 

A combination of a cranberry and a boysenberry would therefore be called a "boysecranberry" or a "craboysenberry", for example. 

Your job is to write a program that computes such a shortest name for a combination of two given fruits. Your algorithm should be efficient, otherwise it is unlikely that it will execute in the alloted time for long fruit names. 
 

 

Input
Each line of the input contains two strings that represent the names of the fruits that should be combined. All names have a maximum length of 100 and only consist of alphabetic characters.

Input is terminated by end of file. 
 

 

Output
For each test case, output the shortest name of the resulting fruit on one line. If more than one shortest name is possible, any one is acceptable.
 

 

Sample Input
apple peach
ananas banana
pear peach
 
Sample Output
appleach
bananas
pearch
 
题意:将两个字符串结合起来,他们的公共子串只输出一次
思路:LCS处理以后逆序输出  标记路径的方法值得学习,如果字母不相同的话就看 当前i和j谁能影响前面的公共字母个数 。
#include 
#include 
#include 
#include
#include
#define ll long long int
#define M 6
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int dp[107][107];
int mark[107][107]; //0表示为公共字母  1表示i-1没有贡献  -1表示j-1没有贡献 
string s,t;
void output(int i,int j){ //打印路径 
//    cout<
    if(i==0||j==0){
        if(i==0)
            for(int k=0;k)
                cout<<t[k];
        else
            for(int k=0;k)
                cout<<s[k];
        return ;
    } 
    if(mark[i][j]==0){
        output(i-1,j-1);
        cout<1];
    }else if(mark[i][j]==-1){
        output(i-1,j);
        cout<1];
    }else{
        output(i,j-1);
        cout<1];
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>s>>t){
        memset(dp,0,sizeof(dp));
        memset(mark,0,sizeof(mark));
        int len1,len2;
        len1=s.length(); len2=t.length();
        for(int i=1;i<=len1;i++)
            for(int j=1;j<=len2;j++){
                if(s[i-1]==t[j-1]){  
                    dp[i][j]=dp[i-1][j-1]+1;
                    mark[i][j]=0;
                }else if(dp[i][j-1]>dp[i-1][j]){
                    dp[i][j]=dp[i][j-1];
                    mark[i][j]=1;
                }else{
                    dp[i][j]=dp[i-1][j];
                    mark[i][j]=-1;
                }
            }
        output(len1,len2);
        cout<<endl;
    }
    return 0;
}

 


推荐阅读
  • 优化SQL Server批量数据插入存储过程的实现
    本文介绍了一种改进的SQL Server存储过程,用于生成批量插入语句。该方法不仅提高了性能,还支持单行和多行模式,适用于SQL Server 2005及以上版本。 ... [详细]
  • 探讨ChatGPT在法律和版权方面的潜在风险及影响,分析其作为内容创造工具的合法性和合规性。 ... [详细]
  • 本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符,并提供了多种编程语言的实现示例。 ... [详细]
  • 利用决策树预测NBA比赛胜负的Python数据挖掘实践
    本文通过使用2013-14赛季NBA赛程与结果数据集以及2013年NBA排名数据,结合《Python数据挖掘入门与实践》一书中的方法,展示如何应用决策树算法进行比赛胜负预测。我们将详细讲解数据预处理、特征工程及模型评估等关键步骤。 ... [详细]
  • 中科院学位论文排版指南
    随着毕业季的到来,许多即将毕业的学生开始撰写学位论文。本文介绍了使用LaTeX排版学位论文的方法,特别是针对中国科学院大学研究生学位论文撰写规范指导意见的最新要求。LaTeX以其精确的控制和美观的排版效果成为许多学者的首选。 ... [详细]
  • 丽江客栈选择问题
    本文介绍了一道经典的算法题,题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈,并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]
  • JSOI2010 蔬菜庆典:树结构中的无限大权值问题
    本文探讨了 JSOI2010 的蔬菜庆典问题,主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性,提出了有效的解决方案,并详细解释了算法的实现过程。 ... [详细]
  • 本文介绍如何使用MFC和ADO技术调用SQL Server中的存储过程,以查询指定小区在特定时间段内的通话统计数据。通过用户界面选择小区ID、开始时间和结束时间,系统将计算并展示小时级的通话量、拥塞率及半速率通话比例。 ... [详细]
  • 国际高保真音乐流媒体平台的崛起:亚马逊与谷歌的竞争策略
    近期,亚马逊和谷歌正积极筹备推出高保真音乐流媒体服务,预计在2019年底前上线。根据市场研究机构CIRP的数据,截至2018年12月,美国智能音箱的安装量已增至6600万台,较第三季度增长显著。这一趋势对Spotify等传统流媒体平台构成了新的挑战。 ... [详细]
  • 深入解析 Android IPC 中的 Messenger 机制
    本文详细介绍了 Android 中基于消息传递的进程间通信(IPC)机制——Messenger。通过实例和源码分析,帮助开发者更好地理解和使用这一高效的通信工具。 ... [详细]
  • 主板IO用W83627THG,用VC如何取得CPU温度,系统温度,CPU风扇转速,VBat的电压. ... [详细]
  • 本文探讨了如何通过预处理器开关选择不同的类实现,并解决在特定情况下遇到的链接器错误。 ... [详细]
  • CSS高级技巧:动态高亮当前页面导航
    本文介绍了如何使用CSS实现网站导航栏中当前页面的高亮显示,提升用户体验。通过为每个页面的body元素添加特定ID,并结合导航项的类名,可以轻松实现这一功能。 ... [详细]
  • 深入解析动态代理模式:23种设计模式之三
    在设计模式中,动态代理模式是应用最为广泛的一种代理模式。它允许我们在运行时动态创建代理对象,并在调用方法时进行增强处理。本文将详细介绍动态代理的实现机制及其应用场景。 ... [详细]
  • 本文将详细介绍如何在没有显示器的情况下,使用Raspberry Pi Imager为树莓派4B安装操作系统,并进行基本配置,包括设置SSH、WiFi连接以及更新软件源。 ... [详细]
author-avatar
关圣钊
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有