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

推荐阅读

include
深入解析C语言中的大小端字节序存储机制

在C语言中，当编译器执行“创建变量”的指令时，会为该变量在内存中分配相应的存储空间。对于整型变量，其值通常以二进制补码形式存储。此外，不同系统采用的大端或小端字节序对数据的实际存储方式有显著影响，理解这些机制有助于开发者更好地控制数据的读写过程。 ... [详细]

蜡笔小新 2024-10-25 18:16:14
include
如何在C++中定位数组中特定数字的最后一个位置

如何在C++中定位数组中特定数字的最后一个位置 ... [详细]

蜡笔小新 2024-10-25 15:20:30
include
c语言中阶乘的精确值

对于大数的操作，可能超出int，甚至long的表示范围，对此，可以使用数组来存储大数，下列代码为求1000以内数的阶乘的代码，代码如下：#include&amp; ... [详细]

蜡笔小新 2024-10-25 13:38:18
include
判断两棵二叉搜索树是否结构相同

在解决此问题时，最初对输入格式的理解存在困惑，导致编写代码过程中出现多次错误。通过参考他人代码，最终明白输入包含两个测试案例：一个案例中有4个节点，需要进行两次结构对比；另一个案例有2个节点，只需进行一次对比。输出结果应为“是”或“否”，以表明两棵树的结构是否相同。 ... [详细]

蜡笔小新 2024-10-24 11:11:24
include
C++核心知识点回顾与深化

虽然经常使用C++，但一些细节可能并不常用。通过查阅资料，回顾了几点重要的细节。首先，建议在构造函数的初始化列表中对成员对象进行初始化，而不是在构造函数体内，这样可以提高代码的效率和可读性。此外，还探讨了其他几个关键概念，如常量成员函数、引用计数和智能指针的使用等。这些内容对于深入理解和高效使用C++至关重要。 ... [详细]

蜡笔小新 2024-10-25 19:48:24
include
PAT甲级 1068 寻找更多硬币 (30分) 01背包问题与路径优化

PAT甲级 1068 寻找更多硬币 (30分) 01背包问题与路径优化 ... [详细]

蜡笔小新 2024-10-25 18:13:20
include
Android数组截取技巧及JNI数组交互在仓库构建中的应用分析

在Android开发中，数组截取技巧和JNI数组交互在仓库构建中的应用具有重要意义。JNI提供了两种主要的数组处理方法：一是生成原生层数组的副本，二是直接通过数组指针进行操作。在进行字符串处理时，如果需要执行其他复杂操作，可以结合这两种方法以提高效率和灵活性。此外，合理利用这些技术可以显著提升应用程序的性能和稳定性。 ... [详细]

蜡笔小新 2024-10-25 15:30:56
include
Qt如何正确的显示、修改表格(QTableView)的内容

安装Qt时，Qt\Qt5.x.x文件夹下自动安装了example文件夹，其中包含了大量的示例。这里根据Examples\Qt-5.5\widgets\t ... [详细]

蜡笔小新 2024-10-25 14:04:53
include
C/C++利用栈和队列实现停车场管理系统【C++教程】

数据结构的课程设计一般都不是很好理解，今天小编为大家总结了一下c和c++版本的常见栈和队列的的停车场管理程序，需要 ... [详细]

蜡笔小新 2024-10-25 13:50:51
include
杭电 HDU 2717 Catch That Cow

CatchThatCowTimeLimit:50002000MS(JavaOthers)MemoryLimit:3276832768K(JavaOt ... [详细]

蜡笔小新 2024-10-25 12:12:19
format
深入解析MySQL Replication中的并行复制机制与实例应用【MySQL进阶教程】

本文深入探讨了MySQL 5.6版本后引入的并行复制机制，详细解析了其工作原理及优化效果。通过具体实例，展示了如何在实际环境中配置和使用并行复制，以提高数据同步效率和系统性能。 ... [详细]

蜡笔小新 2024-10-25 11:28:50
include
C++标准库实现INI文件的读写操作类

本文介绍了一个基于C++标准库实现的INI文件读写操作类。该类在现有网络资源的基础上进行了扩展和优化，增加了获取当前可执行文件路径和宽字节与多字节字符串转换的功能。通过这些增强功能，该类能够更好地适应各种应用场景，提高代码的可移植性和健壮性。具体实现细节请参见 `IniFileSTL.h` 文件。 ... [详细]

蜡笔小新 2024-10-24 17:16:00
include
无IP模拟实验——探索神秘的幻方世界

幻方是一种独特的数学结构，由1至N×N的数字组成N×N的矩阵，其中每一行、每一列以及两条对角线上的数字之和均相等。对于奇数阶的幻方，可以通过特定的方法进行构建。首先，将数字1放置在第一行的中间位置，然后按照一定的规则逐步填充其余数字，最终形成一个完美的幻方。这种构造方法不仅展示了数学的美妙，还为研究者提供了一个探索数字排列规律的独特视角。 ... [详细]

蜡笔小新 2024-10-24 14:47:29
include
图像拼接技术深入解析：基于OpenCV 3.4的Stitching模块源码分析（下篇）

本文继续深入探讨图像拼接技术，特别是在OpenCV 3.4的Stitching模块中的源码实现。通过与VLFeat的SIFT实现进行对比，详细分析了OpenCV在图像特征提取、匹配及拼接过程中的关键算法和技术细节，为读者提供了全面的技术解析和实践指导。 ... [详细]

蜡笔小新 2024-10-24 09:58:40
include
bzoj1923 [Sdoi2010]外星千足虫压位+高斯消元

这个题手动压位非常麻烦，因为对于同一块，后加的数比先加的数小，所以判断最后一位的时候需要定位到最后一块最小的数，而且在找元的时候还不能找到这个位置注意块的总数每个是30个不要存错， ... [详细]

蜡笔小新 2024-10-25 13:00:31

mofa007_903

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

Tags | 热门标签

RankList | 热门文章