【数字动态规划】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
JSOI2010 蔬菜庆典：树结构中的无限大权值问题

本文探讨了 JSOI2010 的蔬菜庆典问题，主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性，提出了有效的解决方案，并详细解释了算法的实现过程。 ... [详细]

蜡笔小新 2024-12-22 18:57:48
int
紫荆花之恋：动态树上的小精灵友谊问题

本题来自WC2014，题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系，要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]

蜡笔小新 2024-12-22 14:36:54
int
解决Visual Studio Code中JavaScript智能感知和自动完成功能异常

探讨如何修复Visual Studio Code中JavaScript的智能感知和自动完成功能在特定场景下无法正常工作的问题，包括配置检查、语言模式选择以及类型注释的使用。 ... [详细]

蜡笔小新 2024-12-21 21:12:34
int
优化C++项目中的JSON处理：选择高性能的RapidJSON库

在高并发需求的C++项目中，我们最初选择了JsonCpp进行JSON解析和序列化。然而，在处理大数据量时，JsonCpp频繁抛出异常，尤其是在多线程环境下问题更为突出。通过分析发现，旧版本的JsonCpp存在多线程安全性和性能瓶颈。经过评估，我们最终选择了RapidJSON作为替代方案，并实现了显著的性能提升。 ... [详细]

蜡笔小新 2024-12-21 18:13:59
int
JavaScript 基础语法指南

本文详细介绍了 JavaScript 的基础语法，包括变量、数据类型、运算符、语句和函数等内容，旨在为初学者提供全面的入门指导。 ... [详细]

蜡笔小新 2024-12-23 10:54:44
int
利用决策树预测NBA比赛胜负的Python数据挖掘实践

本文通过使用2013-14赛季NBA赛程与结果数据集以及2013年NBA排名数据，结合《Python数据挖掘入门与实践》一书中的方法，展示如何应用决策树算法进行比赛胜负预测。我们将详细讲解数据预处理、特征工程及模型评估等关键步骤。 ... [详细]

蜡笔小新 2024-12-23 09:07:40
int
深入理解C++ map的删除与交换操作

本文详细介绍了C++中map容器的多种删除和交换操作，包括clear、erase、swap、extract和merge方法，并提供了完整的代码示例。 ... [详细]

蜡笔小新 2024-12-23 08:29:59
int
CodeChef 2014 April Challenge - Chef的最终对决：数据结构与整体二分的应用

本题探讨了在大数据结构背景下，如何通过整体二分和CDQ分治等高级算法优化处理复杂的时间序列问题。题目设定包括节点数量、查询次数和权重限制，并详细分析了解决方案中的关键步骤。 ... [详细]

蜡笔小新 2024-12-22 19:34:39
int
解决QT交叉编译时遇到的qatomic_i386.h:132错误

在进行QT交叉编译时，可能会遇到与目标架构不匹配的宏定义问题。例如，当为ARM或MIPS架构编译时，需要确保使用正确的宏（如QT_ARCH_ARM或QT_ARCH_MIPS），而不是默认的QT_ARCH_I386。本文将详细介绍如何正确配置编译环境以避免此类错误。 ... [详细]

蜡笔小新 2024-12-22 19:19:44
int
Qt QTableView 内嵌控件的实现方法

本文详细介绍了在 Qt QTableView 中嵌入控件的多种方法，包括使用 QItemDelegate、setIndexWidget 和 setIndexWidget 结合布局管理器。每种方法都有其适用场景和优缺点。 ... [详细]

蜡笔小新 2024-12-22 18:03:16
int
矩阵芯片移动游戏

题目描述：给定一个N*M的网格，初始时网格中有k个芯片，每个芯片的位置已知。玩家可以在每一步操作中将所有芯片沿同一方向移动一格。如果芯片到达边界，则保持不动。目标是通过一系列操作，使每个芯片依次访问指定的目标位置。 ... [详细]

蜡笔小新 2024-12-22 17:38:34
int
使用栈实现字符串中括号匹配的C++程序

本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现，并详细解释了算法的核心思想和具体实现步骤。 ... [详细]

蜡笔小新 2024-12-22 11:44:35
int
字符串中特定字符的移除方法

本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符，并提供了多种编程语言的实现示例。 ... [详细]

蜡笔小新 2024-12-22 00:08:06
int
阿里云ecs怎么配置php环境,阿里云ecs配置选择

阿里云ecs怎么配置php环境,阿里云ecs配置选择 ... [详细]

蜡笔小新 2024-12-23 11:12:07
int
深入解析动态代理模式：23种设计模式之三

在设计模式中，动态代理模式是应用最为广泛的一种代理模式。它允许我们在运行时动态创建代理对象，并在调用方法时进行增强处理。本文将详细介绍动态代理的实现机制及其应用场景。 ... [详细]

蜡笔小新 2024-12-21 15:46:52

mofa007_903

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

Tags | 热门标签

RankList | 热门文章