当前位置: 首页 > news >正文

【动态规划模板】最长公共|上升子序列问题

最长公共子序列🍉

给定两个长度分别为N和M的字符串A和B,求既是A的子序列又是B的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含一个长度为N的字符串,表示字符串A。

第三行包含一个长度为M的字符串,表示字符串B。

字符串均由小写字母构成。

输出格式

输出一个整数,表示最大长度。

数据范围

1 ≤ N,M ≤ 1000。

输入样例:

4 5
acbd
abedc

输出样例:

3

AC Code

N=1010if __name__=='__main__':n,m=map(int,input().split())a,b=' '+input(),' '+input() #创建字符串,表示序列f=[[0]*N for i in range(N)]for i in range(1,n+1):for j in range(1,m+1):f[i][j]=max(f[i-1][j],f[i][j-1])if a[i]==b[j]:f[i][j]=max(f[i][j],f[i-1][j-1]+1)print(f[n][m])

最长上升子序列🍉

给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N 个整数,表示完整序列。

输出格式

输出一个整数,表示最大长度。

数据范围

1≤ N ≤ 1000.

-10**9 ≤ 数列中的数 ≤ 10**9

输入样例:

7
3 1 2 1 8 5 6

输出样例:

4

AC Code:

n=int(input())
p=list(map(int,input().split()))
f=[1]*1005for i in range(n):ans=1for j in range(i):if p[i]>p[j]:ans=max(ans,f[j]+1)f[i]=ansans=1
for i in range(n):ans=max(ans,f[i])
print(ans)

相关文章:

【动态规划模板】最长公共|上升子序列问题

最长公共子序列🍉 给定两个长度分别为N和M的字符串A和B,求既是A的子序列又是B的子序列的字符串长度最长是多少。 输入格式 第一行包含两个整数 N 和 M。 第二行包含一个长度为N的字符串,表示字符串A。 第三行包含一个长度为M的字符串&am…...

Android系统启动流程--zygote进程的启动流程

在上一篇init进程启动流程中已经提到,在init中会解析一个init.rc文件,解析后会执行其中的命令来启动zygote进程、serviceManager进程等,下面我们来看一下: //文件路径:system/core/init/init.cppstatic void LoadBoot…...

C++程序设计——异常

一、C异常概念 异常处理是一种处理错误的方式,当一个函数发现自己无法处理的错误时,就可以抛出异常,让函数的直接或间接的调用者处理这个错误。 (1)throw:当问题出现时,程序会通过throw关键字抛…...

2022年第十三届蓝桥杯web开发—东奥大抽奖【题目、附官方解答】

冬奥大抽奖 介绍 蓝桥云课庆冬奥需要举行一次抽奖活动,我们一起做一个页面提供给云课冬奥抽奖活动使用。 准备 开始答题前,需要先打开本题的项目代码文件夹,目录结构如下: ├── css │ └── style.css ├── effect.g…...

一份两年前一个月的工作经历没写在简历上,背调前主动坦白,却被背调公司亮了红灯,到手的offer没了!...

只因为简历上漏写了一份一个月的工作,就被亮了背调红灯,这公平吗?一位网友就被狠狠坑了一把,来看下他的遭遇:他有一份两年前、时长一个月的工作经历没写在简历上,背调前主动和背调公司还有招聘方hr都说了这…...

C++游戏分析与破解方法介绍

1、C游戏简介 目前手机游戏直接用C开发的已经不多,使用C开发的多是早期的基于cocos2dx的游戏,因此我们这里就以cocos2d-x为例讲解C游戏的分析与破解方法。 Cocos2d-x是一个移动端游戏开发框架,可以使用C或者lua进行开发,也可以混…...

食堂总是拥挤不堪?解决用餐拥挤,教你一招

随着近几年科技的快速发展,行业里出现了很多新的名词,比如智慧社区、智慧旅游、智慧建筑,那么智慧食堂是什么呢?它又是如何实现全自助、全智能消费? 在先进的智能技术以及市场需求带动下,智慧食堂经历了由传…...

ubuntu系统安装时 MBR和GPT的区别

主引导记录(Master Boot Record , MBR)是指一个存储设备的开头 512 字节。它包含操作系统的引导器和存储设备的分区表。   全局唯一标识分区表(GUID Partition Table,缩写:GPT)是一个实体硬盘…...

我在windows10下,使用msys64 mingw64终端

系列文章目录 文章目录系列文章目录前言一、MSYS2是什么?前言 msys2官网 MSYS2 (Minimal SYStem 2) 是一个MSYS的独立改写版本,主要用于 shell 命令行开发环境。 同时它也是一个在Cygwin (POSIX 兼容性层&#xff09…...

个人2023FALL CS申请总结(PhD/MPhil/保研夏令营)

个人2023FALL CS申请总结(PhD/MPhil/保研夏令营)写在最前个人BG及申请情况个人BG申请情况MPhilPhD收获一句话总结:心态爆炸没用,脸皮够厚够勇就行 写在最前 真是一场恶战。有几天,我每天早上都海投几封套瓷邮件&…...

【优化算法】使用遗传算法优化MLP神经网络参数(TensorFlow2)

文章目录任务查看当前的准确率情况使用遗传算法进行优化完整代码任务 使用启发式优化算法遗传算法对多层感知机中中间层神经个数进行优化,以提高模型的准确率。 待优化的模型: 基于TensorFlow2实现的Mnist手写数字识别多层感知机MLP # MLP手写数字识别…...

CAM类激活映射 |神经网络可视化 | 热力图

文章目录前言:安装库:分类案例--ResNet50分割案例AttributeError: ‘tuple‘ object has no attribute ‘cpu‘RuntimeError: grad can be implicitly created only for scalar outputsTypeError: cant convert cuda:0 device type tensor to numpy. Use…...

RecyclerView+BaseRecyclerViewAdapterHelper显示不全只显示第一行item的解决问题

RecyclerViewBaseRecyclerViewAdapterHelper显示不全只显示第一行item,我懵了…,我不说多,直接说吧 先看一下适配器代码中的convert()方法: class MineRadioAdapter(layoutResId: Int R.layout.item_my_live) :BaseQuickAdapte…...

解决后端无法对前端的ajax请求重定向

本章目录: 问题描述 AJAX请求后端直接重定向失败解决方案 后端拦截请为响应头添加重定向标志后端拦截器为响应头添加重定向路径前端响应拦截器获取响应头数据,并通过location.href url 完成页面跳转一、问题描述 本来想在拦截器里设置未登录用户访问指…...

【Python】1分钟就能制作精美的框架图?太棒啦

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录前言一、准备二、基本使用与例子1.初始化与导出2.节点类型3.集群块4.自定义线的颜色与属性总结前言 Diagrams 是一个基于Python绘制云系统架构的模块,它能…...

淘宝必备的补单技巧及注意事项!

补单,是优化善后的s单。单只是模拟用户的购物习惯,而补单同时还要模拟整个店铺的综合数据,包括点击率、转化率等等,补到略高于同行、竞品的平均数据时,淘宝会判断为买家比较喜欢你的商品,从而给你更多推荐机…...

【实用篇】SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式,系统详解springcloud分布式

文章目录一、服务拆分1.1 服务拆分Demo1.2 微服务远程调用二、Eureka2.1 Eureka原理2.2 Eureka-server服务搭建2.3 eureka-client服务注册2.4 eureka-client服务复制2.5 eureka服务发现三、Ribbon负载均衡3.1 负载均衡原理3.2 负载均衡策略3.3 自定义负载均衡策略3.4 饥饿加载与…...

私人飞机、公务机包机会成为富豪圈的主流出行方式吗?

从炫耀性消费到按需使用,私人飞机的消费群体正在被拓宽,但离“成为主流”还有一段距离。“时间就是金钱”为有钱人消费私人飞机提供合理动机,而这群高净值人群的数量增长则成为撑起市场基本面。据相关数据显示,2018年全球超级富豪…...

Oracle组织架构

组织架构 (一)业务组(BG) (二)法律实体(LE) (三)业务实体(OU) (四)库存组织(INV) …...

最小公倍数

目录 最小公倍数 程序设计 程序分析 最小公倍数 【问题描述】给定两个正整数,计算这两个数的最小公倍数。 【输入形式】输入包含多组测试数据,每组只有一行,包括两个不大于1000的正整数. 【输出形式】 对于每个测试用例,给出这两个数的最小公倍数,每个实例输出一行。…...

二叉树的后序遍历(力扣145)

目录 题目描述: 解法一:递归法 解法二:迭代法 解法三:Morris遍历 二叉树的后序遍历 题目描述: 给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。 示例 1: 输入:root …...

《Effective C++》读书纪实 -- 诸君同享

文章目录《Effective C》是一本经典的C编程指南,共包含50条C编程的最佳实践。 确定你的构造函数的行为 在构造函数中,应该尽可能地避免调用虚函数、非静态成员函数和虚基类的函数。 尽量使用const、enum、inline替换#define 使用const、enum、inline可以…...

【云原生】K8S-ConfigMap 实现应用和配置分离

文章目录前言ConfigMap 背景ConfigMap 创建方式ConfigMap 的使用使用 ConfigMap 的注意事项总结前言 Kubernetes 是目前最流行的容器编排系统之一,它提供了丰富的功能来支持容器化应用程序的管理和部署。 ConfigMap 是 Kubernetes 中重要的资源对象,用…...

java -测距工具(经纬度)

代码 /*** 测距工具* author qb*/ public class DistanceUtils {/*** 赤道半径*/private static final double EARTH_RADIUS 6378.137;private static double rad(double d) {return d * Math.PI / 180.0;}/*** Description : 通过经纬度获取距离(单位:米)* Group…...

postgres分区表的创建-基于继承

参考文档: http://postgres.cn/docs/12/ddl-partitioning.html 创建基于继承的分区表的步骤 1 创建父表 2 创建子表,从父表继承过来 3 创建函数及触发器,使插入的数据根据规则,插入到对应的子表中 -- 创建父表 CREATE TABLE a…...

Docker应用部署

文章目录Docker 应用部署一、部署MySQL二、部署Tomcat三、部署Nginx四、部署RedisDocker 应用部署 一、部署MySQL 搜索mysql镜像 docker search mysql拉取mysql镜像 docker pull mysql:5.6创建容器,设置端口映射、目录映射 # 在/root目录下创建mysql目录用于存…...

使用golang实现日志收集系统的logagent

整体架构 参考 七米老师的日志收集项目 主要用go实现logagent的部分,logagent的作用主要是实时监控日志追加的变化,并将变化发送到kafka中。 之前我们已经实现了 用go连接kafka并向其中发送数据,也实现了使用tail库监控日志追加操作。 我们…...

小红书点赞不显示怎么回事?小红书笔记评论被吞怎么办

小红书作为一个互联网产品,是一个软件。既然是软件就会有一定的程序漏洞,这是无法避免的。但是很多时候其实并不一定是漏洞的问题。今天就来和大家谈谈小红书点赞不显示怎么回事,小红书评论被吞又是怎么一回事,这些难道都是程序性…...

地址变换和缺页置换习题

1.设某进程页面的访问序列为4,3,2,1,4,3,5,4,3,2,1,5,当分配给该进程的内存页框数分别为3和4时,对于先进先出,最近最少使用,最佳页面置换算法,分别发生多少次缺页中断? 答: 分配的…...

PAT 乙级 1010 一元多项式求导(解题思路+AC代码)

题目: 设计函数求一元多项式的导数。(注:xn(n为整数)的一阶导数为nxn−1。) 输入格式: 以指数递降方式输入多项式非零项系数和指数(绝对值均为不超过 1000 的整数)。数字间以空格分…...

wordpress更改固定连接后404/aso关键词排名优化是什么

什么是Hibernate Hibernate是一个开放源代码的对象关系映射框架,它对JDBC进行了非常轻量级的对象封装,它将POJO与数据库表建立映射关系,是一个全自动的orm框架,hibernate可以自动生成SQL语句,自动执行,使得…...

wordpress 付费下载/长沙百度快照优化排名

找1-3三个你所做的创新的关键词 分别在IEEE,sci-hub,知网上按以上关键词查找会议,期刊...

计算机专业有哪些/seo精灵

head元素元素包含了所有的头部标签元素可以添加在头部区域的元素标签为:title,style,meta,link,script,noscript,base定义不同文档的标题。定义了浏览器工具栏的标题。当网页添加到收藏夹时,显示在收藏夹中的标题。显示在搜索引擎结果页面的标题。eg: 我是标题 标签…...

做网站图片代码怎么居中/汽车品牌推广策划方案

一、布尔运算——选区的操作1.新选区:新绘制的选区每次都形成一个新选区2.添加到选区:新绘制的选区与之前绘制的选区进行相加(快捷方法先按住shift再绘制新选区)3.从选区减去:新绘制的选区与之前绘制的选区进行相减(快捷方法先按住alt再绘制新…...

天津网站建设普斯泰/百度查重

Flutter 在 Build完成后的监听和每一帧绘制完成后的监听 这个是我们监听要用的重要的类------->WidgetsBinding 官方是这么描述它的 The glue between the widgets layer and the Flutter engine. 中文的意思是 控件层和Flutter引擎之间的粘合剂。就是这个类 它能监听到…...

上海的网站公安备案查询系统/东莞seo公司

from pathlib import Path FILE Path(__file__).absolute() sys.path.append(FILE.parents[0].as_posix())...