问题1016--47幸运数字

1016: 47幸运数字

时间限制: 1 Sec  内存限制: 128 MB
提交: 76  解决: 41
[提交] [状态] [讨论版] [命题人:]

题目描述

罗老师认为4和7是幸运数,对于一个正整数,罗老师定义了其幸运值,这个幸运值就是这个数中4和7数量差的绝对值。比如23, 47, 47714这些数字的幸运值是0;4474,7070这些数的幸运值是2。
现在罗老师想知道,给定A,B,统计A到B之间每个数字幸运值的总和。比如A=40,B=47。其中40,41,42,43,45和46幸运值是1,44幸运值是2,47幸运值是0,所以总和是6*1+2+0=8

输入

输入两个正整数A,B

输出

输出幸运值总和

样例输入 Copy

40 47

样例输出 Copy

8

提示

【样例说明】
其他样例
输入
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)
阶段:按高位到低位,因为高位可以借位低位

来源/分类