【数字动态规划】HDU2089避免62与HDU3555炸弹问题深入解析

作者：mofa007_903 | 来源：互联网 | 2024-10-25 00:07

本文深入探讨了数字动态规划中的两类经典问题：HDU2089“避免62”和HDU3555“炸弹问题”。通过分析这些题目，我们重点讨论了如何在数字序列中查找特定子串的存在性，无论是单个数字还是两位数。通过动态规划的方法，记录已满足的前缀条件，可以高效地解决这类问题。具体而言，本文详细介绍了状态转移方程的设计和优化技巧，帮助读者更好地理解和应用数字动态规划。

这是碰到的第一类数位dp：找这个数是否存在子串为一个一位数，或两位数

其实都一样，记录已经满足前几位即可。

特定的：

如果前面计算对后面有影响，计算前驱的值ten[]

hud 2089

初学，根据我自己的理解码代码，无限wa，不知道是错在哪里，后来强行手跑代码，发现先前的理解不准确。

数位dp的记忆化搜索不能理解为边爆搜边记录，这样是没有意义的（之前脑子懵）。

它的搜索只是搜了（0000~0009），记录到dp数组，然后根据其搜10次（001X~009X），以此类推。

wa代码

#include #include #include #include #include #include #include #include #include typedef long long LL; using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") const int INF=0x3f3f3f3f; const int N = 20; const double eps = 1e-6;int dp[N]; //0->10^i-1 int ten[N],f[N]; void init() {ten[0] = 1;for(int i = 1; i <10; i++)ten[i] = ten[i-1]*10; } int dfs(int pos,int num,int limit,int pre) {if(pos == -1)return num;if(!limit && dp[pos] != -1){if(num) return ten[pos+1];else return dp[pos+1];}int top = limit ? f[pos]:9;//printf("pos = %d top = %d\n",pos,top);int ans = 0;for(int i = 0; i <= top; i++)ans += dfs(pos-1,num||(i==4)||(i==2&&pre==6),limit && i==f[pos],i);if(!limit)dp[pos+1] = ans;return ans; }int main() {init();int a,b;while(~scanf("%d%d",&a,&b) && a,b){memset(dp,-1,sizeof(dp));int pos = 0;int aa = a-1;while(aa){f[pos++] = aa%10;aa /= 10;}int suma = dfs(pos-1,0,1,0);//printf("%d\n",suma);memset(dp,-1,sizeof(dp));pos = 0;int bb = b;while(bb){f[pos++] = bb%10;bb /= 10;}int sumb = dfs(pos-1,0,1,0);printf("%d\n",b-a+1-(sumb-suma));}return 0; }

ac代码

#include #include #include #include #include #include #include #include #include typedef long long LL; using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") const int INF=0x3f3f3f3f; const int N = 20; const double eps = 1e-6;int dp[N][3]; //0->10^i-1 dp[i][2]表示有4或有62的个数,dp[i][1]表示首位有6的个数,dp[i][0]表示没有任何不吉利特征的个数 int ten[N],f[N]; void init() {ten[0] = 1;for(int i = 1; i <10; i++)ten[i] = ten[i-1]*10; } int dfs(int pos,int num,int limit) {if(pos == 0)return num==2;if(!limit && dp[pos][num] != -1)return dp[pos][num];int top = limit ? f[pos]:9;int ans = 0;for(int i = 0; i <= top; i++){if(num == 2 || (num==1&&i==2) || i==4)ans += dfs(pos-1,2,limit&&i==f[pos]);else if(i == 6)ans += dfs(pos-1,1,limit&&i==f[pos]);elseans += dfs(pos-1,0,limit&&i==f[pos]);}if(!limit)dp[pos][num] = ans;return ans; }int solve(int a) {int pos = 0;while(a){f[++pos] = a%10;a /= 10;}return dfs(pos,0,1); } int main() {init();int a,b;memset(dp,-1,sizeof(dp));while(~scanf("%d%d",&a,&b) && a,b){int suma = solve(a-1);int sumb = solve(b);printf("%d\n",b-a+1-(sumb-suma));}return 0; }

同一类型 hud 3555

#include #include #include #include #include #include #include #include #include typedef long long LL; using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") const int INF=0x3f3f3f3f; const int N = 25; const double eps = 1e-6;LL dp[N][3]; //0->10^i-1 dp[i][2]表示49的个数,dp[i][1]表示首位是4的个数,dp[i][0]表示不包含49和4的个数 LL ten[N]; int f[N];//void init() //{ // ten[0] = 1; // for(int i = 1; i // ten[i] = ten[i-1]*10; //} LL dfs(int pos,int zt,int limit) {if(pos == 0)return zt==2;if(!limit && dp[pos][zt] != -1) {return dp[pos][zt];}int top = limit ? f[pos]:9;LL ans = 0;for(int i = 0; i <= top; i++){if(zt==2 || (zt==1&&i==9))ans += dfs(pos-1,2,limit && i==f[pos]);else if(i==4)ans += dfs(pos-1,1,limit && i==f[pos]);elseans += dfs(pos-1,0,limit && i==f[pos]);}if(!limit)dp[pos][zt] = ans;return ans; }LL solve(LL a) {int pos = 0;while(a){f[++pos] = a%10;a /= 10;}return dfs(pos,0,1); } int main() {int T;scanf("%d",&T);memset(dp,-1,sizeof(dp));while(T--){LL n;scanf("%I64d",&n);printf("%I64d\n",solve(n));}return 0; }

推荐阅读

int
hlg_oj_1116_选美大赛

hlg_oj_1116_选美大赛这题是最长子序列，然后再求出路径就可以了。开始写的比较乱，用数组什么的，后来用了指针就好办了。现在把代码贴 ... [详细]

蜡笔小新 2024-11-22 09:20:30
int
深入理解函数式编程中的函子

函子（Functor）是函数式编程中的一个重要概念，它不仅是一个特殊的容器，还提供了一种优雅的方式来处理值和函数。本文将详细介绍函子的基本概念及其在函数式编程中的应用，包括如何通过函子控制副作用、处理异常以及进行异步操作。 ... [详细]

蜡笔小新 2024-11-21 20:29:15
int
UVALive 8201 - BBP 公式计算圆周率

在1995年，Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后，Bailey 和 Borwein 在他们的论文中发表了这一发现，这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]

蜡笔小新 2024-11-21 18:32:57
int
Singleton单例模式和DoubleChecked Locking双重检查锁定模式

问题描述现在，不管开发一个多大的系统（至少我现在的部门是这样的），都会带一个日志功能；在实际开发过程中 ... [详细]

蜡笔小新 2024-11-21 15:14:45
int
无向图中的最小环问题

本问题涉及在给定的无向图中寻找一个至少包含三个节点的环，该环上的节点不重复，并且环上所有边的长度之和最小。目标是找到并输出这个最小环的具体方案。 ... [详细]

蜡笔小新 2024-11-21 15:01:34
int
洛谷 P4009 汽车加油行驶问题解析

探讨了经典算法题目——汽车加油行驶问题，通过网络流和费用流的视角，深入解析了该问题的解决方案。本文将详细阐述如何利用最短路径算法解决这一问题，并提供详细的代码实现。 ... [详细]

蜡笔小新 2024-11-21 14:21:38
int
深入理解C++构造函数

本文详细介绍了C++中的构造函数，包括其定义、特点以及如何通过构造函数进行对象的初始化。此外，还探讨了转换构造函数的概念及其在不同情境下的应用，以及如何避免不必要的隐式类型转换。 ... [详细]

蜡笔小新 2024-11-21 10:41:14
int
自定义字符串连接函数（避免使用标准库函数）

本文介绍如何手动实现一个字符串连接函数，该函数不依赖于C语言的标准字符串处理函数，如strcpy或strcat。函数原型为void concatenate(char *dest, char *src)，其主要作用是将源字符串src追加到目标字符串dest的末尾。 ... [详细]

蜡笔小新 2024-11-20 17:39:42
int
二叉搜索树转换为排序双向链表的面试题解析

本文探讨了一道经典的面试问题，即将给定的一棵二叉搜索树转换为一个排序的双向链表，过程中不允许创建新节点，仅能通过调整现有节点的指针来实现转换。 ... [详细]

蜡笔小新 2024-11-20 17:09:57
int
Linux命令操作指南：返回文件头与桌面的方法

本文介绍了在Linux环境下如何有效返回命令行状态、上一级目录及快速查找头文件和函数定义的方法。包括处理长时间运行命令、编辑器退出技巧、目录导航以及文件搜索策略。 ... [详细]

蜡笔小新 2024-11-20 16:56:14
int
探究64位Linux系统下32位程序的兼容性问题——以OpenVPN为例

本文通过分析一个具体的案例，探讨了64位Linux系统对32位应用程序的兼容性问题。案例涉及OpenVPN客户端在64位系统上的异常行为，通过逐步排查和代码测试，最终定位到了与TUN/TAP设备相关的系统调用兼容性问题。 ... [详细]

蜡笔小新 2024-11-20 16:34:58
int
linux网络子系统分析（二）—— 协议栈分层框架的建立

目录一、综述二、INET的初始化2.1INET接口注册2.2抽象实体的建立2.3代码细节分析2.3.1socket参数三、其他协议3.1PF_PACKET3.2P ... [详细]

蜡笔小新 2024-11-20 15:21:14
int
c语言二元插值,二维线性插值c语言

c语言二元插值,二维线性插值c语言 ... [详细]

蜡笔小新 2024-11-20 12:20:16
int
Qt中信号与槽机制对比传统回调函数的优势

在Qt框架中，信号与槽机制是一种独特的组件间通信方式。本文探讨了这一机制相较于传统的C风格回调函数所具有的优势，并分析了其潜在的不足之处。 ... [详细]

蜡笔小新 2024-11-20 10:48:37
int
嵌套列表的扁平化处理

本文介绍了一种方法，用于遍历嵌套列表中的每个元素。如果元素是整数，则将其添加到结果数组中；如果元素是一个列表，则递归地遍历这个列表。此方法特别适用于处理复杂数据结构中的嵌套列表。 ... [详细]

蜡笔小新 2024-11-20 10:31:42

mofa007_903

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章