程序设计思维与实践 Week10 作业 B LIS & LCS_给定两个单调递增的整数序列a和b,两个序列长度不一定等长,-程序员宅基地

技术标签：程序设计思维与实践验收

题目描述：

给定两个序列A和B。
求序列A的LIS和序列AB的LCS的长度。

注意，LIS为严格递增的，即a1<a2<…<ak(ai<=1,000,000,000)。

input：

第一行两个数n，m（1<=n<=5,000,1<=m<=5,000）
第二行n个数，表示序列A
第三行m个数，表示序列B

output：

输出一行数据ans1和ans2，分别代表序列A的LIS和序列AB的LCS的长度

思路：

最长严格上升子序列：

状态：定义 f i 表示以 ai 为结尾的最长上升序列的方程。

初始化：f = 1，即：f数组全部初始化为1

转移过程:fi=max{fi,fj+1(j<i且aj<ai)}

输出答案：max{f[i], i=1…n}

时间复杂度：O(n^2)

最长公共子序列：

状态：假设 f[i][j] 为 a1 ,a2 , …, ai 和b1 , b2 , …, bj 的 LCS 长度

初始 f[1][0]=0;f[0][1]=0;f[0][0]=0;

转移方程：1.当 ai==bj 时，f[i][j]=f[i-1][j-1]+1 2.否则 f[i][j]=max(f[i-1][j], f[i][j-1])

输出答案：f[n][m]

时间复杂度：O(nm)

#include<iostream>
using namespace std;
int n,m,ans1,a[5010],b[5010];
int f1[5010],f2[5010][5010];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f1[i]=1;
	}
	for(int i=1;i<=m;i++)
	cin>>b[i];
	ans1=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		if(a[i]>a[j])
		f1[i]=max(f1[j]+1,f1[i]);
		ans1=max(ans1,f1[i]);
	}
	f2[1][0]=0,f2[0][1]=0,f2[0][0]=0;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	  if(a[i]==b[j])
	  f2[i][j]=f2[i-1][j-1]+1;
	  else f2[i][j]=max(f2[i][j-1],f2[i-1][j]);
	cout<<ans1<<" "<<f2[n][m];
	return 0;
}

本文链接：https://blog.csdn.net/cax1165/article/details/105705059

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

唯一可译码c语言编程,c语言对尾随后缀法的唯一可译码判断-程序员宅基地

文章浏览阅读938次。#include#includevoidmain(){chara[100][10],F[100][5];inti,j,k,t,T,s1,s2,s3,s4,N;intn=0,m=0;printf("输入你要判断的码组个数:\n");Scanf("%d",&N);printf("输入你要判断的码组:\n");for(i=0;iscanf("%s",a[i]);printf("输入的码是..._唯一可译码尾随后缀

3分钟手把手Studio One 6.6.1中文破解版2024最新图文安装激活教程_studioone中文版-程序员宅基地

文章浏览阅读4.8k次，点赞22次，收藏29次。Studio One6.6.1是一款非常实用的数字音乐创作软件，专门用于创作现代化音乐，软件具有简洁的界面和强大的功能，能够很好地辅助用户创作音乐。顾名思义就是“一个工作室”的意思，它所倡导的制作理念是直接在一个制作软件里完成音乐制作的全部，包括前期的制作缩混和后期的母带处理，所以该软件有两种工作模式，一种是“Song”歌曲前期制作模式，另一种则是“Project”后期母带处理。想想这也很好啊，一个制作平台搞定一切工作，省去在不同软件间的转来转去。_studioone中文版

【附源码】JAVA计算机毕业设计小区物业管理系统(源码+mysql+文档)-程序员宅基地

文章浏览阅读375次，点赞8次，收藏3次。随着城市化进程的快速推进，居住小区成为城市居民生活的主要环境。信息技术的发展为物业管理带来了革新，通过引入先进的管理系统，可以极大地提高管理效率，优化服务质量，实现资源的合理分配和使用。因此，开发一个更为高效、智能的小区物业管理系统0b380，以适应新时代背景下的管理需求，成为了一个亟待解决的问题。智能化的物业管理系统还有助于提升小区的整体形象和品质，吸引更多的住户，增加物业的市场竞争力。随着智慧城市建设的推进，小区物业管理系统0b380的开发将为未来智慧社区的建设打下坚实的基础，促进社会的和谐与进步。

5种五种回归模型及其优缺点_为什么岭回归很少有人用-程序员宅基地

文章浏览阅读3.4w次，点赞7次，收藏60次。参考资料：https://mp.weixin.qq.com/s/mr83EK24S94b_UUlecyqlA 线性回归对异常值非常敏感多项式拟合如果指数选择不当，容易过拟合。岭回归标准线性或多项式回归在特征变量之间存在很高的共线性（high collinearity，比如变量x1与x2之间存在函数关系）的情况下将失败。共线性是自变量之间存在近似线性关系，你所..._为什么岭回归很少有人用

Java实现Excel导入和导出，看这一篇就够了(珍藏版)_java导出excel-程序员宅基地

文章浏览阅读10w+次，点赞1k次，收藏5.2k次。前言最近抽了两天时间，把Java实现表格的相关操作进行了封装，本次封装是基于POI的二次开发，最终使用只需要调用一个工具类中的方法，就能满足业务中绝大部门的导入和导出需求。环境准备1. Maven 依赖本次工具类的封装主要依赖于阿里巴巴的JSON包，以及表格处理的POI包，所以我们需要导入这两个库的依赖包，另外，我们还需要文件上传的相关包，毕竟我们在浏览器页面，做Excel导入时，是上传的Excel文件。<dependency> _java导出excel

python中scale的用法_在netCDF4和Python中使用scale_factor和add_offset的示例？-程序员宅基地

文章浏览阅读1.5k次。如果您想知道如何使用add_offset和scale_factor参数来打包或解包.nc文件中的数据，可以读取here。使用python(download NCEP reanalysis I data for example)读取netCDF4文件时，可以引用以下代码：>>> import netCDF4 as nc>>> file_obj = nc.Datas..._nc文件 scale_factor

随便推点

python开发的游戏手机上玩_利用Python开发游戏脚本，就凭一个设定，玩家直接起飞！...-程序员宅基地

文章浏览阅读809次。前言最近在玩儿公主连结，之前也玩儿过阴阳师这样的游戏，这样的游戏都会有个初始号这样的东西，或者说是可以肝的东西。当然，作为一名程序员，肝这种东西完全可以用写代码的方式帮我们自动完成。游戏脚本其实并不高深，最简单的体验方法就是下载一个Airtest了，直接截几个图片，写几层代码，就可以按照自己的逻辑玩儿游戏了。当然，本篇文章不是要讲Airtest这个怎么用，而是用原始的python+opencv来实..._用python写的文字小游戏怎么用手机玩

历史遗留问题1-Oracle Mysql如何存储数据、索引-程序员宅基地

文章浏览阅读811次，点赞29次，收藏29次。在学习到Oracle redo和undo时，涉及到很多存储结构的知识，但是网上的教程都不是很详细，就去复习了一下mysql，感觉是不是开源的问题，Mysql的社区和知识沉淀远高于Orale，对于初学者很友好，我想请问深入学习这些知识学要怎么去了解，不会和win一样要打入内部吧！！！（本篇文章都是主观理解，作者自己知识的梳理，错误可能有点多）

ANSA二次开发 - Visual Studio Code上搭建ANSA二次开发环境_meta 二次开发-程序员宅基地

文章浏览阅读1.2k次。文章目录Integrating with Microsoft Visual Studio CodeIntroductionANSA and META autocompletionInstallation InstructionsSetting up in Microsoft Visual Studio CodeIntegrating with Microsoft Visual Studio CodeIntroductionVisual Studio Code is a source code edit_meta 二次开发