hdu 2089 不要62 (数位dp模板题,附带详细解释)

题目链接
题意:问区间[n,m]中,不含数字4,也不含数字串“62”的所有数的个数。

思路:可以转化成求区间[0,x]

第一次接触数位dp,参考了这几篇博客。

不要62(数位dp)解题报告

解题报告2

解题报告3

比较重要的前提:

¨对于一个小于n的数,肯定是从高位到低位出现某一位<n的那一位。
¨如 n = 58 n为十进制数。
¨  x = 49 此时x的十位<n
¨  x = 51 此时x的个位<n
¨有了上述性质,我们就可以从高到低枚举第一次<n对应位是哪一位。
这样之前的位确定了,之后的位就不受n的限制即从00…0~99…9,可以先预处理
以及写成递归形式代码会简洁很多,所以就写了递归形式。
更详细的解释参加代码注释。

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

4 评论 在 "hdu 2089 不要62 (数位dp模板题,附带详细解释)"

提醒
排序:   最新 | 最旧 | 得票最多

为什么最后答案只要dfs(len, false, true)呢?dfs(len, true, true) 为什么不用算上?

宽神太强辣。抱紧大腿orz

wpDiscuz