hdu 2089 不要62

题意:

统计区间 [a,b] 中不含 4 和 62 的数字有多少个。

一开始写了一个预处理的版本,死活对不了,只好改成了dfs的,一开始还有理解问题,但是想通了就好了。

dp[i][0/1]表示第i位,上一位是否为6的方案数。

然后记忆化搜索,就这样。

数位dp模板题

 

6 + 9 =