「数位动规练习」准考证

2014年12月13日3,4160

escription

蒟蒻hzwer NOIP2014惨跪,他依稀记得他的准考证号是37,现在hzwer又将要面临一场比赛,他希望准考证号不出现37(连续),同时他又十分讨厌4,所以也不希望4出现在准考证号中。。。现在他想知道在A和B之间有多少合法的准考证号

Input

包含两个整数,A B

Output

一个整数。

Sample Input

「输入样例一」
1 10
「输入样例二」
25 50

Sample Output

「输出样例一」
9
「输出样例二」
14
「数据规模和约定」
20%
的数据,满足 1 <= A <= B <= 1000000 。
100%
的数据,满足 1 <= A <= B <= 2000000000 。

题解

f(i,j)表示长度i,开头为j的合法方案

则f(i,j)= ∑ f(i-1,k) (k≠4,j≠4,k≠7 or j≠3)

套数位dp模板

 

avatar
  Subscribe  
提醒