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

动态规划-数位DP

今天开始做关于数位DP的问题,首先对于数位DP来说,这类问题难度较大,比较难理解,所以博主也会尽量讲的更加详细一些,来帮助大家更好地理解这里的相关知识。

前置知识:

1.首先对于数位DP来说,主要解决的是关于在一段数的范围里,求解所含特殊条件的字符的数的个数。例如在[1,100]之间寻找包括7的数字个数。

2.数位dp的dp数组一般设置为dp[pos][snt][cnt],其中pos表示数字代表的位数,snt表示当前位数是否合法,cnt表示数位合法的个数。

3.一般数位dp中有bool形的limit参数,当limit=true时表示对当前数位有限制,后面的数字不能不能直接使用0-9作为处理,当limit=true时是不能用来做记忆化处理的。

从前有一个国王,他十分热爱数字,他认为数字的优雅程度可以从它们的位数上体现出来。数字的“优雅程度”越高,就越能够吸引他的眼球。他定义,只要一个正整数的十进制表示中包含不超过 3 个非零数字,就被认为是优雅的数字。例如,3、2000、123 是优雅的数字,而 4321、12306、120086 则不是。

这个国王曾经让他的数学家寻找一定范围内所有的优雅数字。但这些数学家并不满足于简单地列出这些数字,他们想要创造一个故事,使得这些数字更加有生命力、更加有意义。于是他们提出了一个挑战:给出一个数字区间,计算其中有多少个优雅的数字。你能够帮助这些数学家完成他们的任务吗?

输入格式

输入包含多个测试用例。

每个测试用例的第一行包含一个整数 T (1≤T≤102),表示要考虑的数字区间的数量。

接下来 T 行,每行包含两个整数 Li​ 和 Ri​ (1≤Li​≤Ri​≤1018),表示一个区间的左右端点。

输出格式

对于每个测试用例,输出一个整数,表示相应区间中优雅数字的数量。

#include <bits/stdc++.h>
using namespace std;
using ll =long long;
ll dp[20][2][20];
int a[20];
ll dfs(int pos,bool snt,bool limit,int cnt){if(pos<0)return (int)(cnt<=3);if(!limit&&dp[pos][snt][cnt]!=-1)return dp[pos][snt][cnt];ll res=0;int up=limit?a[pos]:9;for(int i=0;i<=up;i++){res+=dfs(pos-1,snt||(i>0),limit&&(i==up),cnt+(i>0));}if(!limit)dp[pos][snt][cnt]=res;return res;
}ll f(ll b){int pos=0;while(b){a[pos++]=b%10;b/=10;}return dfs(pos-1,false,true,0);
}
int main()
{int t;cin>>t;while(t--){memset(dp,-1,sizeof(dp));ll a,b;cin>>a>>b;cout<<f(b)-f(a-1)<<'\n';}return 0;
}

分析

1.在数位动态规划中,return (int)(cnt <= 3) 这行代码是递归终止条件的核心逻辑,其作用是判断当前构造的数字是否符合 “优雅数字” 的定义。当 pos < 0 时,表示已经处理完数字的所有位(例如,对于三位数 123pos 从最高位 2 递减到 0,处理完最低位后 pos 变为 -1)。此时,递归需要返回一个结果,用于统计符合条件的数字数量。

2.为什么 limit == true 时不能记忆化?

假设我们正在处理数字 123,并递归到百位为 1(最高位)的状态:

此时 limit == true,百位只能选 0 或 1。若百位选 0,后续的十位和个位可以任意选(0-9);若百位选 1,后续的十位只能选 0-2(受原数字 123 的限制)。

如果我们在 limit == true 时记录了这个状态的结果,当处理其他数字(如 456)时,同样的状态(例如 pos=2, st=true, cnt=1)可能会复用错误的结果(因为 456 的百位可以选 0-4,与 123 的限制不同)。

3.snt的作用:处理前置0,一般的数位dp中都会有snt用来处理前置0,但本道题因为都是正整数,所以并没有处理前置0.

4.记忆化的本质:记录已计算的状态结果

关键点dp[pos][st][cnt] 存储的是当前状态在无限制(limit=false)时的结果。这个结果是在枚举完当前位的所有可能取值并计算出总和后才能确定的,因此必须在递归调用结束并累加到 res 之后才能记录。

今天的分享就到这里,关于这个类型的dp是比较难以理解的,希望大家可以收藏做做,麻烦大家多多关注,后续博主也将继续分享相关的内容。

http://www.xdnf.cn/news/10982.html

相关文章:

  • C++实现汉诺塔游戏用户交互
  • C++ 变量一
  • Java并发编程实战 Day 5:线程池原理与使用
  • MySQL 搜索特定桩号距离之间的数据
  • Linux网络基础概念(1)
  • 三、Sqoop 全量导入核心命令
  • 振动力学:有阻尼单自由度系统(简谐力激励的受迫振动)
  • 蚂蚁感冒--思维
  • linux常用特殊字符
  • The Elastic Stack 简介
  • 云原生架构的演进与落地:重塑企业 IT 的核心能力
  • 深度思考:摆脱无效忙碌的核心策略
  • windows可视化粘贴使用剪贴板
  • 在 RAG 系统中引入 DuckDuckGo:隐私优先的检索增强实践
  • 【大模型】ChatGLM训练框架
  • CMS32M65xx/67xx系列CoreMark跑分测试
  • 工业协议修改器:让ModbusRTU485与Profibus无障碍对话
  • SpringBoot核心注解详解及3.0与2.0版本深度对比
  • Python爬虫解析动态网页:从渲染到数据提取
  • CapCut(剪映国际版)软件及安装教程
  • 基于新课标的中小学人工智能课程教学解决方案
  • 基于大模型的短暂性脑缺血发作(TIA)全流程预测与诊疗辅助系统详细技术方案
  • 如何在 DataGrip 中 连接 Databend
  • 客户线索商机怎么管?客户线索商机管理工具哪个好?
  • 【数学】高斯积分+伽马函数公式自用背诵笔记
  • 互联网c++开发岗位偏少,测开怎么样?
  • uboot ping不了
  • 在Windows下编译出llama_cpp_python的DLL后,在虚拟环境中使用方法
  • Delphi 设置文件 永久只读
  • java30