数位dp

HDU2089，属于数位dp入门系列。
多做做应该就会了。
 1 #include<iostream>
 2 #include<cstdio> 
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cstring>
 7 #include<map>
 8 #include<set>
 9 #define f(i,a,b) for(int i=a;i<=b;i++)
10 #define ll long long
11 #define scan(i) scanf("%d",&i)
12 #define scand(i) scanf("%lf",&i)
13 #define scanl(i) scanf("%lld",&i)
14 #define pii pair<int,int>
15 #define pb push_back
16 #define dbg(args...) cout<<#args<<" : "<<args<<endl; 
17 #define pf printf
18 //#define mp make_pair
19 using namespace std;
20 int n,m;
21 int a[50];
22 int dp[50][2];
23 //dp[i][j]表示符合要求的，开头是i的数的个数
24 int dfs(int pos,int pre,int sta,bool limit){
25     //pos枚举哪一位，pre左边一位是什么，sta左边一位是不是6，limit到没到顶 
26     if(pos==-1){
27         return 1;
28     }
29     if(limit==false&&dp[pos][sta]!=-1){
30         return dp[pos][sta];
31     }
32     int up;
33     if(limit==true){
34         up=a[pos];
35     }
36     else{
37         up=9;
38     }
39     int tmp=0;
40     f(i,0,up){
41         if(pre==6&&i==2){
42             continue; 
43         }
44         if(i==4) continue;
45         if(limit==true&&i==a[pos]){
46             tmp+=dfs(pos-1,i,i==6,true);
47         }
48         else tmp+=dfs(pos-1,i,i==6,false);    
49     }
50     if(limit==false) dp[pos][sta]=tmp;
51     return tmp;    
52 }
53 int solve(int x){
54     int pos=0;
55     while(x){
56         a[pos]=x%10;
57 //        dbg(pos);
58 //        dbg(a[pos]);
59         pos++;
60         x/=10;
61     }
62 //    dbg(pos);
63     return dfs(pos-1,-1,0,true);
64 }
65 int main(){
66     int l,r;
67     memset(dp,-1,sizeof(dp));
68     while(scanf("%d%d",&l,&r)!=EOF){
69         if(l==0&&r==0) return 0;
70         
71 //        dbg(l);
72 //        dbg(r);
73 //        dbg(solve(l-1));
74 //        dbg(solve(r)); 
75         pf("%d
",solve(r)-solve(l-1));
76     }
77 }