HDU2089不要62数位DP入门
前言
上学期差不多整个学期都在打各种比赛,几乎没学新算法,因此寒假好好补一波算法,不过数位DP入个门也花了我两天,学习效率还没回来… …
模板题
给定一个数字区间[l,r],问你区间内有多少数不含4,也不含连续的62。
题目范围是1e7,可以On预处理+前缀和O1查询,代码就不放了。
数位DP
今天的重点是数位DP。
数位DP的好处在于直接对位进行暴力,另外加上记忆化,可以大大减少时间。例如枚举千位时,一次枚举就相当于暴力下的一千次枚举。
初学数位DP,我感觉他的本质就是记忆化搜索。因此先上无记忆化的搜索代码:
1 |
|
上面这份代码的写法其实比较奇怪,算是半个数位DP的写法吧。其中的lim是数位dp中一个关键点,可以看底下的参考博客理解。
这份代码本质上就是暴力,如果查询次数多或者数据范围加到1e9以上肯定是会TLE的,但是加上记忆化就不一样了,记忆化可以剪掉一大部分递归栈。记忆化只多了四五行代码:
1 | /* |
这里的记忆化需要判断!limit,这是一个稍难的点,事实上,就是为了避免limit
或者非limit
两种状态的冲突,经过实测,我们完全可以记忆化中的一种,不过就此题来说,显然!limit的状态更多,因此选择记忆这种效率更高。具体理解看底下的参考博客吧。