蓝桥杯备赛——DP续【python】

一、小明的背包2

试题链接:https://www.lanqiao.cn/problems/1175/learning/

输入示例

5 20
1 6
2 5
3 8
5 15
3 3 

输出示例

120

问题分析

这题是完全背包,每个物品有无数个,所以对于任意dp[i][j](其表示的意思为选到第i个物品时所消耗的体积为j),当j>=i的体积时,其可以从三个状态转移过来,①dp[i-1][j](表示一次也不选i)②dp[i-1][j-w]+v   (表示第一次选i)③dp[i][j-w]+v(表示不一定第一次选i),把②去掉答案也是对的;当j<i时,只能从dp[i-1][j]转移来啦。


代码示例

N,V=map(int,input().split())
dp=[[0]*(V+1) for _ in range(N+1)]
for i in range(1,N+1):w,v=map(int,input().split())for j in range(1,V+1):if j-w>=0:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v,dp[i][j-w]+v)else:dp[i][j]=dp[i-1][j]
print(dp[N][V])

二、最长公共子序列

试题链接:https://www.lanqiao.cn/problems/1189/learning/

输入示例

5 6
1 2 3 4 5
2 3 2 1 4 5

输出示例

4

问题分析

dp[i][j]表示数组A处理到第i个数,数组B处理到第j个数时他们的最大公共子序列的长度。分为两种情况:①a[i]==b[j],那么dp[i][j]=dp[i-1][j-1]+1;②a[i]!=b[j],dp[i][j]=max(dp[i-1][j],dp[i][j-1])


代码示例

N,M=map(int,input().split())
a=[0]+input().split()
b=[0]+input().split()
dp=[[0]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):for j in range(1,M+1):if a[i]==b[j]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[N][M])

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/334561.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2005-2022年各省全体居民人均可支配收入数据(无缺失)

2005-2022年各省全体居民人均可支配收入数据&#xff08;无缺失&#xff09; 1、时间&#xff1a;2005-2022年 2、来源&#xff1a;国家统计局、统计年鉴 3、指标&#xff1a;全体居民人均可支配收入 4、范围&#xff1a;31省 5、缺失情况&#xff1a;无缺失 6、指标解释…

redis基本数据结构与应用

文章目录 概要String结构Hash结构List结构Set结构Zset结构bitmap位图类型geo地理位置类型其他常用命令 概要 redis常用的5种不同数据结构类型之间的映射如下&#xff1a; 结构类型结构存储的值结构的读写能力STRING可以是字符串、整数或者浮点数key-value形式&#xff1b;对整…

利用cherry pick巧妙地将某次提交单独合并到其他分支

0. 引言 最近在进行系统的多版本并行开发&#xff0c;涉及一些共有基础功能提交时就遇到了麻烦&#xff0c;一份代码需要向多个版本分支进行同步&#xff0c;以保证多版本都能有更新该基础功能。 多次对比提交的方式显然会带来巨大的工作量。但实际上我们可以通过git的cherry…

鹏哥C语言复习——调试

目录 什么是调试&#xff1f; Debug和Release&#xff1a; 调试方法&#xff1a; 环境准备&#xff1a; 调试快捷键介绍&#xff1a; 调试快捷键注意事项&#xff1a; 监视与内存查看&#xff1a; 数组元素的监视&#xff1a; 编译常见错误归类&#xff1a; 编译型错…

迁移基于MicroBlaze处理器的设计

迁移基于MicroBlaze处理器的设计 生成系统基础设施&#xff08;MicroBlaze、AXI_Interconnect&#xff0c; Clk_Wiz、Proc_Sys_Reset&#xff09; 生成系统基础设施&#xff08;MicroBlaze、AXI_Interconnect、Clk_Wiz和 Proc_Sys_Reset&#xff09;&#xff1a; 1.使用所需的板…

Java 文件操作和输入输出流

在 Java 编程中&#xff0c;文件操作和输入输出流是非常常见和重要的任务&#xff0c;它们允许你读取和写入文件、处理数据流等。 文件操作概述 文件操作是指对文件进行创建、读取、写入、删除等操作的过程。在 Java 中&#xff0c;文件操作通常涉及到使用文件对象、输入输出…

区块链系统开发测试----链码部署开发、系统开发验证

一.检查配置环境 检查虚拟机环境&#xff0c;确保有正在运行的Hyperledger Fabric区块链&#xff0c;并且其中chaincode_basic、credit_chaincode链码可以正常调用 查看chaincode_basic、credit_chaincode链码调用 二.开发征信链码代码 基于现有征信链码&#xff0c;开发征信…

SpringBoot基础篇

1&#xff1a;parent 目的&#xff1a;减少依赖配置 开发SpringBoot程序要继承spring-boot-starter-parentspring-boot-starter-parent中定义了若干个依赖管理继承parent模块可以避免多个依赖使用相同技术出现依赖版本冲突继承parent的形式也可以采用引入依赖的i形式实现效果…

【Python编程实战】基于Python语言实现学生信息管理系统

&#x1f3a9; 欢迎来到技术探索的奇幻世界&#x1f468;‍&#x1f4bb; &#x1f4dc; 个人主页&#xff1a;一伦明悦-CSDN博客 ✍&#x1f3fb; 作者简介&#xff1a; C软件开发、Python机器学习爱好者 &#x1f5e3;️ 互动与支持&#xff1a;&#x1f4ac;评论 &…

SpringBoot整合RabbitMQ的快速使用教程

目录 一、引入依赖 二、配置rabbitmq的连接信息等 1、生产者配置 2、消费者配置 三、设置消息转换器 四、生产者代码示例 1、配置交换机和队列信息 2、生产消息代码 五、消费者代码示例 1、消费层代码 2、业务层代码 在分布式系统中&#xff0c;消息队列是一种重要…

[SWPUCTF 2022 新生赛]奇妙的MD5... ...

目录 [SWPUCTF 2022 新生赛]奇妙的MD5 [GDOUCTF 2023]受不了一点 [LitCTF 2023]作业管理系统 注入点一&#xff1a;文件上传 注入点二&#xff1a;创建文件直接写一句话木马 注入点三&#xff1a;获取数据库备份文件 [LitCTF 2023]1zjs [SWPUCTF 2022 新生赛]奇妙的MD5 …

修改了vue3 <script setup>留言板

Лунная ночь <template><button class"edit_view_checkbox"><input type"checkbox" v-model"editshowInput" value"编辑" /></button><div class"editshowInput" v-if"editshowI…

Oracle实践|内置函数之日期与时间函数

&#x1f4eb; 作者简介&#xff1a;「六月暴雪飞梨花」&#xff0c;专注于研究Java&#xff0c;就职于科技型公司后端工程师 &#x1f3c6; 近期荣誉&#xff1a;华为云云享专家、阿里云专家博主、腾讯云优秀创作者、ACDU成员 &#x1f525; 三连支持&#xff1a;欢迎 ❤️关注…

《中国科技投资》是什么级别的期刊?是正规期刊吗?能评职称吗?

问题解答&#xff1a; 问&#xff1a;《中国科技投资》期刊什么级别&#xff1f; 答&#xff1a;国家级 问&#xff1a;《中国科技投资》期刊是核心期刊吗? 答&#xff1a;不是&#xff0c;是万方维普收录的正规期刊。 主管单位&#xff1a;中国信息协会 主办单位&#…

3.1 掌握RDD的创建

在Apache Spark中&#xff0c;RDD&#xff08;Resilient Distributed Dataset&#xff09;是一个基本的、不可变的、分布式的和可分区的数据集。它能够自动进行容错处理&#xff0c;并支持在大规模集群上的并行操作。RDD之间存在依赖关系&#xff0c;可以实现管道化&#xff0c…

【全开源】民宿酒店预订管理系统(ThinkPHP+uniapp+uView)

民宿酒店预订管理系统 特色功能&#xff1a; 客户管理&#xff1a;该功能可以帮助民宿管理者更加有效地管理客户信息&#xff0c;包括客户的姓名、电话、地址、身份证号码等&#xff0c;并可以在客户的订单中了解客户的消费情况&#xff0c;从而更好地满足客户的需求&#xff…

②单细胞学习-组间及样本细胞比例分析

目录 数据读入 每个样本各细胞比例 两个组间细胞比例 亚组间细胞比例差异分析&#xff08;循环&#xff09; 单个细胞类型亚新间比例差异 ①单细胞学习-数据读取、降维和分群-CSDN博客 比较各个样本间的各类细胞比例或者亚组之间的细胞比例差异 ①数据读入 #各样本细胞…

【介绍下如何在SQL中添加数据】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

rust语言初识

程序设计实践课上水一篇ing 来源&#xff1a;rust基础入门-1.初识rust-酷程网 (kucoding.com) rust作为一名新兴语言&#xff0c;与go又有些许不同&#xff0c;因为它的目标是对标系统级开发&#xff0c;也就是C、C这两位在编程界的位置。比如我们最常用的windows系统&#x…

SpringBoot实现邮箱验证码

自行创建一个SpringBoot项目 导入SpringBoot所需要的邮箱验证码的包 <!--邮件发送--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-mail</artifactId><version>2.6.1</version>…