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

第五十章 动态规划——数位DP模型

第五十章 动态规划——数位DP模型

  • 一、什么是数位DP
    • 数位DP的识别
    • 数位DP的思路
  • 二、例题
    • 1、AcWing 1083. Windy数(数位DP)
    • 2、AcWing 1082. 数字游戏(数位DP)
    • 3、AcWing 1081. 度的数量(数位DP)

一、什么是数位DP

数位DP的识别

当一道题问我们,数轴上,某个区间内的数,满足某个条件的个数。

一般像这种题我们会使用数位DP的逻辑。

数位DP的思路

数位DP顾名思义就是按照数字的每一位去讨论。

那么数位DP做题思路分为两步:按位枚举,分类讨论
在这里插入图片描述
我们把区间的上限X写出来:

那么怎么分类讨论呢?
在这里插入图片描述
从上到下是从高位到低位枚举的,对于每一位我们的分类依据是:(0 ~ a - 1)和a,那么为什么这么分呢?

一般数位DP都是让我们挑选满足某个条件的数,我们不仅需要考虑某个数是否满足条件,还需要考虑某个数是否小于上限值。

那么我们在分类讨论以后,就发现我们分出的第一类情况中:0~a-1,由于高位都小于了a,那么这个数肯定比上限X小,也就是说此时我们只需要考虑是否满足题目中的某个条件。

我们对每一位都做这样的操作,只不过越往下分,每个数字固定的前缀就越长,最后我们会发现所有二叉树的右儿子恰好组成了我们上限值。

那么有人可能会想,题目中问的有可能是个区间,难道我们不需要考虑这个数必须大于等于下限吗?

这里可以使用一个思路,假设f[n]f[n]f[n]是满足所有小于等于上限值的数的数量,我们只需要再减去小于下限m的数目,即f[m−1]f[m - 1]f[m1]的值,就是区间[n,m][n,m][n,m]内符合题目条件的数目。

我们发现上面介绍的仅仅是分类讨论,那和DP有什么关系呢?

其实当我们进行分类讨论后,我们发现左支部分枚举的数是不需要关注他的大小是否超过区间上限的,因此我们只需要考虑它是否满足某个条件,而找出符合该条件的数目的时候往往需要用DP。

二、例题

1、AcWing 1083. Windy数(数位DP)

这道题中要格外注意前导零的问题。
AcWing 1083. Windy数(数位DP)

2、AcWing 1082. 数字游戏(数位DP)

AcWing 1082. 数字游戏(数位DP)

3、AcWing 1081. 度的数量(数位DP)

AcWing 1081. 度的数量(数位DP)

相关文章:

第五十章 动态规划——数位DP模型

第五十章 动态规划——数位DP模型一、什么是数位DP数位DP的识别数位DP的思路二、例题1、AcWing 1083. Windy数(数位DP)2、AcWing 1082. 数字游戏(数位DP)3、AcWing 1081. 度的数量(数位DP)一、什么是数位DP…...

02- pandas 数据库 (机器学习)

pandas 数据库重点: pandas 的主要数据结构: Series (一维数据)与 DataFrame (二维数据)。 pd.DataFrame(data np.random.randint(0,151,size (5,3)), # 生成pandas数据 index [Danial,Brandon,softpo,Ella,Cindy], # 行索引 …...

学Qt想系统的学习,看哪本书?

Qt 是一个跨平台应用开发框架(framework),它是用 C语言写的一套类库。使用 Qt 能为 桌面计算机、服务器、移动设备甚至单片机开发各种应用(application),特别是图形用户界面 (graphical user in…...

2023年网络安全比赛--跨站脚本攻击②中职组(超详细)

一、竞赛时间 180分钟 共计3小时 二、竞赛阶段 1.访问服务器网站目录1,根据页面信息完成条件,将获取到弹框信息作为flag提交; 2.访问服务器网站目录2,根据页面信息完成条件,将获取到弹框信息作为flag提交; 3.访问服务器网站目录3,根据页面信息完成条件,将获取到弹框信息…...

网络安全实验室4.注入关

4.注入关 1.最简单的SQL注入 url:http://lab1.xseclab.com/sqli2_3265b4852c13383560327d1c31550b60/index.php 查看源代码,登录名为admin 最简单的SQL注入,登录名写入一个常规的注入语句: admin’ or ‘1’1 密码随便填,验证…...

领域搜索算法之经典The Lin-Kernighan algorithm

领域搜索算法之经典The Lin-Kernighan algorithmThe Lin-Kernighan algorithm关于算法性能提升的约束参考文献领域搜索算法是TSP问题中的三大经典搜索算法之一,另外两种分别是回路构造算法和组合算法。 而这篇文章要介绍的The Lin-Kernighan algorithm属于领域搜索算…...

深度学习基础-机器学习基本原理

本文大部分内容参考《深度学习》书籍,从中抽取重要的知识点,并对部分概念和原理加以自己的总结,适合当作原书的补充资料阅读,也可当作快速阅览机器学习原理基础知识的参考资料。 前言 深度学习是机器学习的一个特定分支。我们要想…...

C语言操作符详解 一针见血!

目录算数操作符移位操作符位操作符赋值操作符单目操作符关系操作符逻辑操作符条件操作符逗号表达式下标引用、函数调用和结构成员表达式求值11.1 隐式类型转换算数操作符💭 注意/ 除法 --得到的是商% 取模(取余)--得到的是余数如果除法操作符…...

前端面试题汇总

一:JavaScript 1、闭包是什么?利弊?如何解决弊端? 闭包是什么:JS中内层函数可以访问外层函数的变量,外层函数无法操作内存函数的变量的特性。我们把这个特性称作闭包。 闭包的好处: 隔离作用…...

以数据驱动管理场景,低代码助力转型下一站

数据驱动 数据驱动,是通过移动互联网或者其他的相关软件为手段采集海量的数据,将数据进行组织形成信息,之后对相关的信息讲行整合和提炼,在数据的基础上经过训练和拟合形成自动化的决策模型,简单来说,就是…...

2023年全国数据治理DAMA-CDGA/CDGP考试报名到弘博创新

弘博创新是DAMA中国授权的数据治理人才培养基地,贴合市场需求定制教学体系,采用行业资深名师授课,理论与实践案例相结合,快速全面提升个人/企业数据治理专业知识与实践经验,通过考试还能获得数据专业领域证书。 DAMA认…...

流程控制之循环

文章目录五、流程控制之循环5.1 步进循环语句for5.1.1 带列表的for循环语句5.1.2 不带列表的for循环语句5.1.3 类C风格的for循环语句5.2 while循环语句5.2.1 while循环读取文件5.2.2 while循环语句示例5.3 until循环语句5.4 select循环语句5.5 嵌套循环5.4 利用break和continue…...

SpringDataRedis快速入门

SpringDataRedis快速入门1.SpringDataRedis简介2.RedisTemplate快速入门3.RedisSerializer4.StringRedisTemplate1.SpringDataRedis简介 SpringData是Spring中数据操作的模块,包含对各种数据库的集成,其中对Redis的集成模块就叫做SpringDataRedis Spri…...

MySQL 的执行计划 explain 详解

目录 什么是执行计划 执行计划的内容 select子句的类型 访问类型 索引的存在形式...

2023年网络安全比赛--Web综合渗透测试中职组(超详细)

一、竞赛时间 180分钟 共计3小时 二、竞赛阶段 1.通过URL访问http://靶机IP/1,对该页面进行渗透测试,将完成后返回的结果内容作为FLAG值提交; 2.通过URL访问http://靶机IP/2,对该页面进行渗透测试,将完成后返回的结果内容作为FLAG值提交; 3.通过URL访问http://靶机IP/3,对…...

【c++之于c的优化 - 下】

前言 一、inline 概念 以inline修饰的函数叫做内联函数,编译时C编译器会在调用内联函数的地方展开,没有函数调用建立栈帧的开销,内联函数提升程序运行的效率。 如果在上述函数前增加inline关键字将其改成内联函数,在编译期间编译…...

MySQL事务管理

文章目录MySQL事务管理事务的概念事务的版本支持事务的提交方式事务的相关演示事务的隔离级别查看与设置隔离级别读未提交(Read Uncommitted)读提交(Read Committed)可重复读(Repeatable Read)串行化&#…...

二维计算几何全家桶

参考文章&#xff1a;范神的神仙博客 前置芝士 一些高中数学 向量的叉积&#xff1a;向量的点积为 a⋅b∣a∣∣b∣cos⁡<a,b>a\cdot b|a||b|\cos<a,b>a⋅b∣a∣∣b∣cos<a,b>&#xff0c;向量的叉积为 ab∣a∣∣b∣sin⁡<a,b>a\times b|a||b|\sin<…...

基于图的下一代入侵检测系统

青藤云安全是一家主机安全独角兽公司&#xff0c;看名字就知道当前很大一块方向专注云原生应用安全&#xff0c;目前主营的是主机万相/容器蜂巢产品&#xff0c;行业领先&#xff0c;累计支持 800万 Agent。当前公司基于 NebulaGraph 结合图技术开发的下一代实时入侵检测系统已…...

若依框架---树状层级部门数据库表

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是小童&#xff0c;Java开发工程师&#xff0c;CSDN博客博主&#xff0c;Java领域新星创作者 &#x1f4d5;系列专栏&#xff1a;前端、Java、Java中间件大全、微信小程序、微信支付、若依框架、Spring全家桶 &#x1f4…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...