2015 UESTC Training for Dynamic Programming H

H - 邱老师选妹子

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

邱老师长得帅这是人尽皆知，于是追他的妹子就会很多。

但是你知道，邱老师是一个很专一的人，所以他心里面只能有一个人。

于是他决定从追他的众多妹子里挑选一个出来。于是酱神给邱老师出来一个主意，已知有一些妹子，恰好可以给她们从l到r排号，使得每一个妹子有单独的数字，而正好有r-l+1个妹子。

酱神说，我们不能要运气不好的女孩，而酱神又给了两个数字62和4，如果妹子的排号里面有62(必须是连续的)或4，那么就排除他现在给你l和r，问有多少妹子可以有幸在第一轮留下。

Input

输入的都是整数对l、r（0<l≤r<1000000），如果遇到都是0的整数对，则输入结束。

Output

每组数据输出占一行，对于每个l和r 输出有多少个妹子可以在第一轮不被排除

Sample input and output

Sample Input	Sample Output
1 100 0 0	80

Hint

不好的数字为所有含有4或62的号码。例如：

62315 73418 88914

都属于不好的。但是，61152虽然含有6和2，但不是62连号

解题思路：

　　这道题一看就是一个裸裸的数位dp，但是数位dp看课件还是没有学透，在沈爷的指导下，我总算是把数位dp看的差不多了，其实数位dp不难，数位dp又叫按位dp

一般情况下，有一个标准的模式，这个模式记录好后，就是更改sta和newsta的关系了。

代码：

 1 # include<cstdio>
 2 # include<iostream>
 3 # include<fstream>
 4 # include<algorithm>
 5 # include<functional>
 6 # include<cstring>
 7 # include<string>
 8 # include<cstdlib>
 9 # include<iomanip>
10 # include<numeric>
11 # include<cctype>
12 # include<cmath>
13 # include<ctime>
14 # include<queue>
15 # include<stack>
16 # include<list>
17 # include<set>
18 # include<map>
19 
20 using namespace std;
21 
22 const double PI=4.0*atan(1.0);
23 
24 typedef long long LL;
25 typedef unsigned long long ULL;
26 
27 # define inf 999999999
28 # define MAX 1000000+4
29 
30 int num[23];
31 int dp[23][2];
32 
33 
34 int dfs( int len, int sta, int flag )
35 {
36     if ( len == 0 )
37         return 1;
38     if ( flag==0&&dp[len][sta]!=-1 )
39         return dp[len][sta];
40 
41     int ans = 0;
42     int ed = flag?num[len]:9;
43     for (int i = 0; i <= ed;i++)
44     {
45         if ( i == 4||sta&&i==2 )
46             continue;
47         ans += dfs( len-1,i==6,flag&&i==ed );
48         if ( flag == 0 )
49         {
50             dp[len][sta] = ans;
51         }
52     }
53     return ans;
54 }
55 
56 
57 
58 int cal ( int x )
59 {
60     int cnt = 0;
61     while ( x!=0 )
62     {
63         num[++cnt] = x%10;
64         x/=10;
65     }
66     return dfs(cnt,0,1);
67 
68 }
69 
70 int main(void)
71 {
72     int l,r;
73     while ( scanf("%d%d",&l,&r)!=EOF )
74     {
75         if ( l==0&&r==0 )
76             break;
77         memset(dp,-1,sizeof(dp));
78         int ans = cal(r)-cal(l-1);
79         printf("%d
",ans);
80     }
81 
82     return 0;
83 }