蓝桥杯备赛第五篇(动态规划)

news/2024/4/24 17:19:55/文章来源:https://blog.csdn.net/m0_73473352/article/details/136434130

1.数位dp

public class Main {static long[] limit;static int length;static long[][] dp;public static long dfs(int pos, int pre, boolean flag, boolean lead) {if (pos == length) return 1;if (!flag && !lead && dp[pos][pre] != -1) return dp[pos][pre];long max = (flag ? limit[pos] : 进制数);long sum = 0;for (int i = 0; i <= max; i++) {if (条件) {sum += dfs(pos + 1, i, flag && i == limit[pos], lead && i == 0);}}if (!flag && !lead) dp[pos][pre] = sum;return sum;}public static long solve(long num) {if (num == 0) return 1;length = ("" + num).length();limit = new long[length];dp = new long[length][10];for (int i = 0; i < length; i++) {Arrays.fill(dp[i], -1);}for (int i = length - 1; i >= 0; i--) {limit[i] = num % 进制数;num /= 进制数;}return dfs(0, 0, true, true);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int a = scanner.nextInt();int b = scanner.nextInt();System.out.println(solve(b) - solve(a - 1));}
}

2.状态压缩dp

这一部分没有统一的算法模板,只有对二进制操作熟悉之后才能做好这类题,所以我在此总结几个操作。

进行标记:i | (1<<j)
判断是否被标记: (i & (1<<j))==0
判断是否包含:a | b == b
当前行选的元素不能相邻:now & (now >> 1) == 0
当前行与上一行的选择上下也不能相邻:pre & now == 0
注意:添加状态用 | ,删除状态用 ^,判断状态用 &

3.最长公共子序列

public class Main {public static void main(String[] args) {char[] str1 = "abcdefgh".toCharArray();char[] str2 = "acjlfabhh".toCharArray();int[][] dp = new int[str1.length + 1][str2.length + 1];for (int i = 1; i <= str1.length; i++) {for (int j = 1; j <= str2.length; j++) {if (str1[i - 1] == str2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}System.out.println(dp[str1.length][str2.length]);}
}

4.最大连续子序列和

public class Main {public static void main(String[] args) {int[] arr = new int[]{-2, 11, -4, 13, -5, -2};int[] dp = new int[arr.length];dp[0] = arr[0];int max = arr[0];for (int i = 1; i < arr.length; i++) {dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);max = Math.max(max, dp[i]);}System.out.println(max);}
}

5.最长上升子序列

public class Main {public static void main(String[] args) {int[] arr = new int[]{2, 1, 5, 3, 6, 4, 6, 3};int[] dp = new int[arr.length];dp[0] = 1;int max = dp[0];for (int i = 1; i < arr.length; i++) {for (int j = i - 1; j >= 0; j--) {if (arr[i] > arr[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}max = Math.max(max, dp[i]);}}System.out.println(max);}
}

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

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

相关文章

如何学习I2C协议

文章目录 学习I2C协议0 懒人直达1 了解协议开发者2 从恩智浦半导体公司下载官方技术文档3 翻译成中文4 资源下载 学习I2C协议 0 懒人直达 点击直达 1 了解协议开发者 I2C&#xff08;Inter-Integrated Circuit&#xff09;协议是由荷兰皇家飞利浦电子公司&#xff08;现恩智…

Unity Samples和帧动画的问题

拖动序列帧图片和自己创建clip的帧率不同 我今天在创建帧动画的时候用了两种方式第一种是直接拖动序列帧图片到Hierachy&#xff0c;然后生成的第二种是这样我发现两者播放的动画速率不一样最后查了半天查不到原因。最后发现是Samples的原因&#xff0c;而且Unity把Samples这个…

Python数据处理实战(4)-上万行log数据提取并作图进阶版

系列文章&#xff1a; 0、基本常用功能及其操作 1&#xff0c;20G文件&#xff0c;分类&#xff0c;放入不同文件&#xff0c;每个单独处理 2&#xff0c;数据的归类并处理 3&#xff0c;txt文件指定的数据处理并可视化作图 4&#xff0c;上万行log数据提取并作图进阶版&a…

外包干了5天,技术退步明显。。。。。

在湖南的一个安静角落&#xff0c;我&#xff0c;一个普通的大专生&#xff0c;开始了我的软件测试之旅。四年的外包生涯&#xff0c;让我在舒适区里逐渐失去了锐气&#xff0c;技术停滞不前&#xff0c;仿佛被时间遗忘。然而&#xff0c;生活的转机总是在不经意间降临。 与女…

别再盲目推广!用Xinstall精准追踪App下载渠道

在移动互联网时代&#xff0c;App推广已经成为企业获取用户、提升品牌知名度的重要手段。然而&#xff0c;面对众多的推广渠道和复杂的用户行为&#xff0c;如何精准统计App下载渠道来源&#xff0c;成为了广告主和开发者亟待解决的问题。今天&#xff0c;我们就来聊聊国内专业…

Go 互斥锁的实现原理?

Go sync包提供了两种锁类型&#xff1a;互斥锁sync.Mutex 和 读写互斥锁sync.RWMutex&#xff0c;都属于悲观锁。 概念 Mutex是互斥锁&#xff0c;当一个 goroutine 获得了锁后&#xff0c;其他 goroutine 不能获取锁&#xff08;只能存在一个写者或读者&#xff0c;不能同时…

docker 部署prometheus+grafana

首先进行部署docker 配置阿里云依赖&#xff1a; curl -o /etc/yum.repos.d/CentOS-Base.repo https://mirrors.aliyun.com/repo/Centos-7.repo # 配置centos 7的镜像源 yum install -y yum-utils device-mapper-persistent-data lvm2 # 安装一些后期或需要的的一下依…

[Java 探索之路~大数据篇] 新时代大数据流处理入门指南

本文主要介绍大数据基础&#xff0c;以及 flink 流计算 文章目录 【基础知识】1. 批处理与流处理1.批处理2.流处理 2. 为什么需要一个优秀的流处理框架1. 股票交易的业务场景2.生产者——消费者模型3. 流处理框架要解决的诸多问题&#xff08;1&#xff09;可扩展性&#xff08…

2024年腾讯云学生服务器优惠活动「云+校园」政策解读

2024年腾讯云学生服务器优惠活动「云校园」&#xff0c;学生服务器优惠价格&#xff1a;轻量应用服务器2核2G学生价30元3个月、58元6个月、112元一年&#xff0c;轻量应用服务器4核8G配置191.1元3个月、352.8元6个月、646.8元一年&#xff0c;CVM云服务器2核4G配置842.4元一年&…

【C++从0到王者】第五十一站:B+树

文章目录 一、B树1.B树的概念2.B树的特性3.B树的插入的过程4.总结 二、B*树1. B*树的概念2.B*树的分裂 三、总结四、B树系列和哈希和平衡搜索树作对比五、B树的一些应用1.索引2.MySQL索引3.MyISAM2.InnoDB 一、B树 1.B树的概念 B树是B树的变形&#xff0c;是在B树基础上优化的…

C++ 链表OJ

目录 1、2. 两数相加 2、24. 两两交换链表中的节点 3、143. 重排链表 4、23. 合并 K 个升序链表 5、25. K 个一组翻转链表 解决链表题目常用方法&#xff1a; 1、画图 2、引入虚拟"头”结点 便于处理边界情况方便我们对链表操作 3、大胆定义变量&#xff0c;减少连接…

2024-3-7 市场分歧视角

昨天安奈儿市场带领市场情绪一致&#xff0c;新型工业化方向独占鳌头&#xff0c;日内高潮节点尾盘老龙 克来机电涨停&#xff0c;昨晚很多老师在YY老龙是不是要二波了&#xff0c;呵呵。 今天市场分歧从竞价就开始了&#xff0c;隔夜单我记忆中 天奇股份88亿&#xff0c;上海…

python71-Python的函数入门,定义函数和调用函数

在使用函数之前必须先定义函数&#xff0c;定义函数的语法格式如下&#xff1a; def 函数名(形参列表)://由零条到多条可执行语句组成的函数[return [返回值]] Python声明函数必须使用def关键字&#xff0c;对函数语法格式的详细说明如下。 1&#xff09;函数名:从语法角度来…

力扣--从前序与中序遍历序列构造二叉树

题目&#xff1a; 思想&#xff1a; 首先先序遍历能确定根节点的值&#xff0c;此时查看该值在中序遍历中的位置&#xff08;如果索引为i&#xff09;&#xff0c;那么i左侧为左子树&#xff0c;i 右侧为右子树。从中序数组中即可看出左子树结点个数为 i&#xff0c;右子树节点…

Pytorch学习 day06(torchvision中的datasets、dataloader)

torchvision的datasets 使用torchvision提供的数据集API&#xff0c;比较方便&#xff0c;如果在pycharm中下载很慢&#xff0c;可以URL链接到迅雷中进行下载&#xff08;有些URL链接在源码里&#xff09;代码如下&#xff1a; import torchvision # 导入 torchvision 库 # …

线程池不香了? 结构化并发才是王道!

我们先定义获取用户信息任务&#xff1a; 再定义获取订单信息任务&#xff1a; 然后再构造线程池并执行任务&#xff1a; 输出结果为&#xff1a; 看上去一切都刚刚好&#xff0c;但是&#xff0c;如果获取订单信息时出错了&#xff0c;此时会是什么现象呢&#xff1f;修改获取…

PoC免写攻略

在网络安全领域&#xff0c;PoC&#xff08;Proof of Concept&#xff09;起着重要的作用&#xff0c;并且在安全研究、漏洞发现和漏洞利用等方面具有重要的地位。攻击方视角下&#xff0c;常常需要围绕 PoC 做的大量的工作。常常需要从手动测试开始编写 PoC&#xff0c;再到实…

SAP - 采购价格确定 ③ 抬头条件和组条件

抬头条件和组条件 当我们创建一个具有多个行项目的采购订单时,我们经常需要条件可以应用到所有的行项目中。相应的,条件也可以应用到特定的行项目。在R/3系统中,条件可以涉及采购凭证的单个行项目(项目条件),多个行项目(组条件)或所有的行项目(抬头条件)。 一些标准…

计算机/大数据毕业设计-基于Python的动漫数据分析可视化系统的设计与实现

基于Python的动漫数据分析可视化系统的设计与实现 设计爬虫程序爬取哔哩哔哩动漫数据信息 后端使用flask框架&#xff0c;数据库使用Mysql8.0&#xff0c;可视化使用echarts 部分代码如下&#xff1a; # 保存所有动漫信息 all_anime_infos [] # 保存到文件中 file_writer …

讨论:5万官网是建站界的劳斯莱斯了吧,到了软件开发领域呢?

如题&#xff0c;所以赛道选择很重要&#xff0c;当然难度系数也不一样。能花5万元做官网的&#xff0c;凤毛麟角&#xff0c;如果是做软件开发&#xff0c;5万元顶多算个起步价&#xff0c;老铁们&#xff0c;是这样吗&#xff1f;