算法笔记——数位DP

一、前置知识

1.DP小知识

D P DP DP 是一种算法思想,用递推方程的方式解决问题。但是使用它要满足如下性质:

  • 最优子结构: 子结构优秀,整个就优秀。
  • 无后效性:当前决策不会影响后面。

2.DP实现方法

众所周知, D P DP DP 可以使用记忆化搜索实现。模板:

int dp[状态];
int dfs(当前状态){if (满足退出条件) return 退出返回值;if (dp[当前状态]!=-1) return dp[当前状态];int ans=0; 辅助变量进行状态转移return dp[当前状态]=ans;
}memset(dp,-1,sizeof(dp));

二、问题提出

给你一个区间 [ l , r ] [l,r] [l,r] 和一个条件,求区间内满足条件的数的个数。

要求复杂度 O ( l o g 10 n ) O(log_{10}n) O(log10n)

三、解决问题

我们以一个具体问题入手:数页码。

看如下树形图:

接下来我们可以设计转移:

int dp[20][210];//dp[i][j]表示i位和为j的数字个数

但是如果改一下:
在这里插入图片描述
我们会发现,有时数位有限制,所以我们要增加一维 l i m lim lim,表示是否有限制。

强调一下: 有的问题会有 前导零的特殊处理方式,则需要加一位 z e ze ze,表示有没有前导零。

四、蓝题解答

windy数。

可以增加一维 p r e pre pre,表示上一位去什么数。(本题涉及前导零,请谨慎思考)。

代码(附带模板):

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[20][10][2][2],num[20],tot;
//id pre lim
int dfs(int id,int pre,int lim,int ze){//位数,前一位 ,限制,前导零//if (id!=tot&&ze)if (id==0) return 1-ze;if (dp[id][pre][lim][ze]!=-1){return dp[id][pre][lim][ze];}int ans=0,up=(lim?num[id]:9);for (int i=0; i<=up; i++){if (abs(pre-i)>=2||ze){ans+=dfs(id-1,i,lim&&(i==up),ze&&(i==0));}}//cout<<id<<" "<<pre<<" "<<lim<<" "<<ze<<" "<<ans<<"\n";return dp[id][pre][lim][ze]=ans;
}int solve(int x){tot=0; memset(dp,-1,sizeof(dp));while (x) num[++tot]=x%10,x/=10;//cout<<tot<<"\n";return dfs(tot,0,1,1); 
}
signed main(){int l,r; cin>>l>>r;cout<<solve(r)-solve(l-1);//cout<<solve(r)<<" "<<solve(l-1);
}

五、特别说明

今天是母亲节,要特别感谢妈妈!

没有她们的大力支持,就没有我们这些 蒟蒻 OIer。

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

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

相关文章

【解决】Android APK文件安装时 已包含数字签名相同APP问题

引言 在开发Android程序过程中&#xff0c;编译好的APK文件&#xff0c;安装至Android手机时&#xff0c;有时会报 包含数字签名相同的APP 然后无法安装的问题&#xff0c;这可能是之前安装过同签名的APP&#xff0c;但是如果不知道哪个是&#xff0c;无法有效卸载&#xff0c;…

Linux——进程间通信

目录 一、进程通信的初步认识 1.1 进程间通信目的 1.2 进程间通信的种类 管道&#xff08;Pipes&#xff09; System V IPC POSIX IPC 三、管道 3.1 知识铺垫 3.2 匿名管道 3.2.1 基本概念 3.2.2 测试用例&#xff1a; 3.3 管道的行为 3.4 命名管道 3.4.1 基本概念…

生产设备数据管控要怎么做 可以实现精益生产和智能制造?

生产设备在制造过程中会产生多种类型的数据&#xff0c;这些数据对于优化生产流程、提高效率、降低成本和预防性维护等方面至关重要。需要对这些数据进行有效的采集和管理&#xff0c;以实现对生产设备数据管控。 一、生产设备数据类型包括&#xff1a; 设备运行状态数据&…

机器学习周报第三十八周 iTransformer

文章目录 week38 iTransformer摘要Abstract一、文献阅读1. 题目2. abstract3. 网络架构**转置Embedding&#xff1a;****LayerNorm&#xff08;层归一化&#xff09;****Feed-forward network&#xff08;前馈网络&#xff09;****Multivariate-Attention&#xff08;多变量注意…

【Linux 网络】网络编程套接字 -- 详解

⚪ 预备知识 1、理解源 IP 地址和目的 IP 地址 举例理解&#xff1a;&#xff08;唐僧西天取经&#xff09; 在 IP 数据包头部中 有两个 IP 地址&#xff0c; 分别叫做源 IP 地址 和目的 IP 地址。 如果我们的台式机或者笔记本没有 IP 地址就无法上网&#xff0c;而因为…

【UnityUI程序框架】The PureMVC Framework[一]底层源码中文详解

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…

推导 模型矩阵的逆转置矩阵求运动物体的法向量

一个物体表面的法向量如何随着物体的坐标变换而改变&#xff0c;取决于变换的类型。使用逆转置矩阵&#xff0c;可以安全地解决该问题&#xff0c;而无须陷入过度复杂的计算中。 法向量变化规律 平移变换不会改变法向量&#xff0c;因为平移不会改变物体的方向。 旋转变换会改…

Python 全栈系列244 nginx upstream 负载均衡 踩坑日记

说明 最初是因为租用算力机(Python 全栈系列242 踩坑记录:租用算力机完成任务)&#xff0c;所以想着做一个负载均衡&#xff0c;然后多开一些服务&#xff0c;把配置写在nginx里面就好了。 一开始租用了一个3080起了一个服务&#xff0c;后来觉得速度不够快&#xff0c;再起了…

基于地平线J6E,「吃蟹者」易航智能重塑高速NOA

作者 |张祥威 编辑 |德新 一批基于地平线J6E的智驾方案将要到来&#xff0c;高速NOA领域很快会变天。 易航智能是这批智驾方案公司中的一家。 近日在北京车展&#xff0c;这家公司推出一套基于地平线J6 E的7V1R方案&#xff0c;可以实现城市记忆领航、高速NOA、记忆泊车、L2…

社交媒体数据恢复:密聊猫

一、概述 密聊猫是一款提供多种优质体验的手机社交聊天软件。通过这款软件&#xff0c;用户可以享受到多种不同的乐趣体验&#xff0c;如真人在线匹配、真实的交友体验等。同时&#xff0c;密聊猫也提供了数据恢复功能&#xff0c;帮助用户找回丢失的数据。 二、数据恢复步骤…

前端Vue架构

1 理解&#xff1a; 创建视图的函数&#xff08;render&#xff09;和数据之间的关联&#xff1b; 当数据发生变化的时候&#xff0c;希望render重新执行&#xff1b; 监听数据的读取和修改&#xff1b; defineProperty&#xff1a;监听范围比较窄&#xff0c;只能通过属性描…

博客互动革命:如何打造活跃读者社区并提升参与度

CSDN 的朋友你们好&#xff0c;我是未来&#xff0c;今天给大家带来专栏【程序员博主教程&#xff08;完全指南&#xff09;】的第 10 篇文章“与读者互动”。本文揭示了提升技术博客参与度的秘诀。从评论互动到社交媒体策略&#xff0c;本文将指导你如何建立强大的读者社区。掌…

blender 为世界环境添加纹理图像

1、打开世界环境配置项 2、点击颜色右侧的黄色小圆&#xff0c;选择环境纹理 3、打开一张天空图像 4、可以通过调整强度/力度&#xff0c;调整世界环境的亮度

传感网应用开发教程--AT指令访问新大陆云平台(ESP8266模块+物联网云+TCP)

实现目标 1、熟悉AT指令 2、熟悉新大陆云平台新建项目 3、具体目标&#xff1a;&#xff08;1&#xff09;注册新大陆云平台&#xff1b;&#xff08;2&#xff09;新建一个联网方案为WIFI的项目&#xff1b;&#xff08;3&#xff09;ESP8266模块&#xff0c;通过AT指令访问…

用python写算法——队列笔记

1.队列定义 队列是一种特殊的线性表&#xff0c;它只允许在表的前端进行删除操作&#xff0c;在表的后端进行插入操作&#xff0c;和栈一样&#xff0c;队列是一种操作受限制的线性表。进行插入操作的端称为队尾&#xff0c;进行删除操作的端称为队头。队列中没有元素时&#…

部署Discuz论坛项目

DIscuz 是由 PHP 语言开发的一款开源社交论坛项目。运行在典型的LNMP/LAMP 环境中。 安装MySQL数据库5.7 主机名IP地址操作系统硬件配置discuz-db192.168.226.128CentOS 7-mini-20092 Core/4G Memory 修改主机名用来自己识别 hostnamectl set-hostname discuz-db #重连远程…

一键复制:基于vue实现的tab切换效果

需求&#xff1a;顶部栏有切换功能&#xff0c;内容区域随顶部切换而变化 目录 实现效果实现代码使用示例在线预览 实现效果 如下 实现代码 组件代码 MoTab.vue <template><div class"mo-tab"><divv-for"item in options"class"m…

OBS插件--视频回放

视频回放 视频回放是一款源插件&#xff0c;它可以将指定源的视频缓存一段时间&#xff08;时间可以设定&#xff09;&#xff0c;将缓存中的视频添加到当前场景中后&#xff0c;可以快速或慢速不限次数的回放。这个功能在类似体育比赛的直播中非常有用&#xff0c;可以捕获指…

网络基础(三)——网络层

目录 IP协议 1、基本概念 2、协议头格式 2.1、报头和载荷如何有效分离 2.2、如果超过了MAC的规定&#xff0c;IP应该如何做呢&#xff1f; 2.3、分片会有什么影响 3、网段划分 4、特殊的ip地址 5、ip地址的数量限制 6、私有ip地址和公网ip地址 7、路由 IP协议 网络…

C++/Qt 小知识记录6

工作中遇到的一些小问题&#xff0c;总结的小知识记录&#xff1a;C/Qt 小知识6 dumpbin工具查看库导出符号OSGEarth使用编出的protobuf库&#xff0c;报错问题解决VS2022使用cpl模板后&#xff0c;提示会乱码的修改设置QProcess调用cmd.exe执行脚本QPainterPath对线段描边处理…