【HDU 2089 不要62】

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2089

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。

Output

对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。

Sample Input

1  100
0  0

Sample Output

80
数位DP模板题,使用记忆化搜索实现。设\(dp[i][0]\)表示长度为\(i\)的数字,在第\(i\)位且前一位不是6的情况下符合条件的数字个数。\(dp[i][1]\)表示长度为\(i\)的数字,在第\(i\)位且前一位是6的情况下符合条件的数字个数。
显然,如果前一位是6,那么这一位不能是2;同时,所有位都不能是4。在枚举每位数字的时候,考虑限制问题,比如上限是210,枚举第一位为1的时候,第二位可以是0~9,但是第一位是2的时候,第二位只能是0或1。也就是说如果前一位达到了区间上界的那一位,那这一位就不能自由取值了,而是最大取区间上界的这一位。我们的\(dp\)数组记录的是无限制的情况,如果有限制,那么直接枚举并返回结果,因为这种情况不是很多,所以复杂度是完全可以接受的。
下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*