当前位置: 首页 > 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的正整数. 【输出形式】 对于每个测试用例,给出这两个数的最小公倍数,每个实例输出一行。…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"&#xff0…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...