【数字动态规划】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; }

推荐阅读

bit
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
char
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
go
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
char
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
go
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
heap
C++实现经典排序算法

本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出，帮助读者全面了解这些排序方法的特点。 ... [详细]

蜡笔小新 2024-12-27 19:25:14
int
C++: 实现基于类的四面体体积计算

本文介绍如何使用C++编程语言，通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式，并提供了两种不同的实现方式。 ... [详细]

蜡笔小新 2024-12-27 14:31:39
char
Java面试题解析

本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]

蜡笔小新 2024-12-27 13:55:14
bit
组合数学问题：棋盘上的组合数计算

本文探讨了如何在模运算下高效计算组合数C(n, m)，并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元，从而实现除法取余的计算。 ... [详细]

蜡笔小新 2024-12-26 21:41:44
char
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
int
C++构造函数与初始化列表详解

本文深入探讨了C++中构造函数的初始化列表，包括赋值与初始化的区别、初始化列表的使用规则、静态成员初始化等内容。通过实例和调试证明，详细解释了初始化列表在对象创建时的重要性。 ... [详细]

蜡笔小新 2024-12-26 14:19:13
char
文件描述符、文件句柄与打开文件之间的关联解析

本文详细探讨了文件描述符、文件句柄和打开文件之间的关系，通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]

蜡笔小新 2024-12-26 14:00:46
text
VxWorks中的双向链表与环形缓冲应用

本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法，通过具体示例代码加深理解。 ... [详细]

蜡笔小新 2024-12-26 13:26:16
char
Linux设备驱动程序：异步时间操作与调度机制

本文介绍了Linux内核中的几种异步延迟操作方法，包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务，而无需阻塞当前线程，从而提高系统的响应性和效率。 ... [详细]

蜡笔小新 2024-12-26 08:55:03
go
魔兽世界：备战策略

本文探讨了《魔兽世界》中红蓝两方阵营在备战阶段的策略与实现方法，通过代码展示了双方如何根据资源和兵种特性进行战士生产。 ... [详细]

蜡笔小新 2024-12-25 19:03:01

mofa007_903

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

Tags | 热门标签

RankList | 热门文章