程序设计思维与实践 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

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

智能推荐

【spring cloud】spring cloud2.X spring boot2.0.4调用feign配置Hystrix Dashboard 和集成Turbine 【解决：Hystrix仪表盘...-程序员宅基地

文章浏览阅读311次。环境：<java.version>1.8</java.version><spring-boot.version>2.0.4.RELEASE</spring-boot.version><spring-cloud.version>Finchley.SR1</spring-cloud.version><lcn.last.v..._springboot 2.4 可以使用feign调用吗

Win7/Win10移动用户文件夹(C:\Users)移到非系统盘(如D:)_该应用程序位于未经授权的位置请移至非系统文件夹-程序员宅基地

文章浏览阅读8.8w次，点赞48次，收藏252次。Windows的用户文件夹默认所在位置是系统盘（通常是C盘）下的“\Users”目录之内。该文件夹中保存着所有的用户个人数据，比如你保存在“桌面”上的文件（实际上是保存在C:\Users\你的用户名\Desktop\目录之中），再比如你保存在“我的文档”里的文件（实际上是保存在C:\Users\用户名\Documents目录之中）。用户文件夹处于系统盘的坏处在于，如若系统盘一旦坏掉，就可能连带用..._该应用程序位于未经授权的位置请移至非系统文件夹

约瑟夫环的数学公式推导_约瑟夫出圈问题公式-程序员宅基地

文章浏览阅读6.7k次，点赞7次，收藏35次。约瑟夫环的数学方法解决编写约瑟夫环程序时会发现，当我们把整个报数过程的人数N变的很大，例如到几百万，虽然在最后还是只剩下两个人报数，但也要循环几百万次才能确定最后留下来的那个人。这样程序执行的效率不高，会占用大量时间去执行循环的过程。有时会发生输出一直等待很长时间才能出来结果。经过查询资料，找到了约瑟夫环的数学解决方法，以及它的算法具体执行的过程来做分享。我们假设..._约瑟夫出圈问题公式

软件测试|Pytest必会使用autouse实现自动传参-程序员宅基地

文章浏览阅读120次。1.薪资丰厚：基本薪资+绩效+项目奖金+年终奖2.福利：和正式员工福利基本看齐，共享工位，免费夜宵，班车，一流办公环境，月末周六双倍工资3.技术栈：C/C+当用例很多的时候，每次。不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦。不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦虑不焦。

基于51单片机冰箱温度控制器设计_基于51单片机的智能冰箱控制系统设计-程序员宅基地

文章浏览阅读871次，点赞11次，收藏3次。*单片机设计介绍，基于51单片机冰箱温度控制器设计。_基于51单片机的智能冰箱控制系统设计

ubuntu创建sftp和ftp服务器及相应的用户管理_ubuntu sftp服务器查看用户和密码-程序员宅基地

文章浏览阅读4.8k次。一、sftp服务器进入root模式（下面的操作默认都是在root用户下）#安装openssh-serverapt-get install -y openssh-server创建sftp的组和用户#创建sftp-users组groupadd sftp-users#创建sftp用户目录alicemkdir /home/alice#创建sftp用户alice，并且绑定其主目..._ubuntu sftp服务器查看用户和密码

随便推点

Linux命令_禅道的运行日志放在哪-程序员宅基地

文章浏览阅读309次。笔记_禅道的运行日志放在哪

Web实训项目--网页设计（附源码）_web前端网页设计代码-程序员宅基地

文章浏览阅读4.3w次，点赞79次，收藏882次。我们要使用这些知识实现一个简单的网页设计，利用HTML的a标签做文本内容跳转以及超链接的应用，CSS设计内容样式和图片、动画、视频的大小位置格式，JavaScript实现轮播图效果等。学习如何设计网页中的轮播图和动画效果，并掌握a标签文本内容跳转、超链接的应用、播放音乐与视频等操作。通过对Web知识内容的了解，我们掌握了HTML、CSS和JavaScript的基本知识以及利用它们实现一些简单的应用。1、使用Web知识实现一个简单的网页设计，利用HTML的a标签做文本内容跳转以及超链接的应用。_web前端网页设计代码