【样例说明】
其他样例
输入
58 526
输出
231
输入
4444 7777
输出
2338
【数据规模和约定】
1<=A<=B<=2,000,000,000
题解:
问题从a~b这段区间中,有多少4、7相差
那么,初始的计算,有4、7相差的数,肯定带4或7的
比如0~99,没带4、7的数没有意义,只有4,7,*4,4*,*7,7*这样的数才可能有相差数
可以先计算0~a-1之中有多少个相差数
再计算0~b之中有多少个相差数
计算0~n之间的4、7相差数可以用DP做:
状态:dp[pos][n4][n7][f],表示从pos到len-1位中,已有4的数量n4,7的数量n7,可否向高位借位,能产生多少个4、7相差数
这个借位表示比如20,如果我在十位取0或1,那么我可以在个位上去0~9任意的数,因为十位没取满,个位可以向十位借位
转移:这是计数类DP,可以枚举第pos为上的数字v,然后加上dfs(pos+1, n4+(v==4), n7+(v==7), f)
阶段:按高位到低位,因为高位可以借位低位