文档章节

Codevs 1408 最长公共子序列

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 470
阅读 5
收藏 0

题目描述 Description
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们要研究最长公共上升子序列了。
小沐沐说,对于两个串A,B,如果它们都包含一段位置不一定连续的数字,且数字是严格递增的,那么称这一段数字是两个串的公共上升子串,而所有的公共上升子串中最长的就是最长公共上升子串了。
奶牛半懂不懂,小沐沐要你来告诉奶牛什么是最长公共上升子串。不过,只要告诉奶牛它的长度就可以了。

输入描述 Input Description
第一行N,表示A,B的长度。
第二行,串A。
第三行,串B。

输出描述 Output Description
输出长度

样例输入 Sample Input
4
2 2 1 3
2 1 2 3

样例输出 Sample Output
2

数据范围及提示 Data Size & Hint
1<=N<=3000,A,B中的数字不超过maxlongint

QAQ现学现卖。刚开始认为先做个最长公共子序列,然后在公共子序列里寻找最长上升子序列发现并不对。。于是还是老老实实学了LCIS(详情自己看讲的很详细)

#include<iostream>
#include<cstdio>

using namespace std;

const int maxn = 3333;
int n,ans,temp,s1[maxn],s2[maxn],f[maxn][maxn];

int main()
{
 cin>>n;
 for(int i=1;i<=n;i++) scanf("%d",&s1[i]);
 for(int j=1;j<=n;j++) scanf("%d",&s2[j]);
 for(int i=2;i<=n;i++)
 {
 temp=0;
 for(int j=1;j<=n;j++)
 {
 f[i][j]=f[i-1][j];
 if(s1[i]>s2[j]&&f[i-1][j]>temp) temp=f[i-1][j];
 if(s1[i]==s2[j]) f[i][j]=temp+1;
 }
 }
 for(int i=0;i<=n;i++) ans=max(ans,f[n][i]);
 cout<<ans<<endl;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/52816910

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
最长公共子序列(LCS)

最长公共子序列,即Longest Common Subsequence,LCS。一个序列S任意删除若干个字符得到新序列T,则T叫做S的子序列;两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序...

klaus丶
2016/02/24
49
0
【动态规划】基础,最长公共子序列问题(LCS)

正文之前 囚徒健身初期感觉还是很温和的,练习起来不吃力,而且对身体的负荷也很小,还是不错的,推荐大家也学习下。。进入正题,最长公共子序列问题 正文 (1)子序列: 一个序列,中任意删除...

HustWolf
2018/07/23
0
0
python实现最长公共子序列的求解

(待完善...) 最长公共子序列是动态规划基本题目,下面按照动态规划基本步骤解出来。 1.找出最优解的性质,并刻划其结构特征 序列a共有m个元素,序列b共有n个元素,如果a[m-1]==b[n-1],那么...

勉旃
2018/09/03
0
0
算法与数据结构(二):动态规划(DP)总结

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/89388883 1. 最长公共子序列 题目描...

dby_freedom
04/21
0
0
删除部分字符使其变成回文串问题——最长公共子序列LCS问题

先要搞明白:最长公共子串和最长公共子序列的区别。 最长公共子串(Longest Common Substirng):连续 最长公共子序列(Longest Common Subsequence,LCS):不必连续 题目:给定一个字符串s...

牧师-Panda
2016/09/10
720
0

没有更多内容

加载失败,请刷新页面

加载更多

java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
今天
6
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
5
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
15
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
16
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部