hdu 2089 不要62 数位dp入门

求出a-b中不含有4以及连续的62的数的个数。
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mem1(a) memset(a, -1, sizeof(a))
 4 int dp[10][10], digit[9], len;
 5 int dfs(int len, bool state, bool fp) {     //state表示这一位是否有限制
 6     if(!len)                                //fp表示len这一位是否只能取到小于等于digit[len]的数， 即这一位能否随便填
 7         return 1;
 8     if(!fp && dp[len][state]!=-1)
 9         return dp[len][state];
10     int ret = 0, maxx = fp?digit[len]:9;
11     for(int i = 0; i<=maxx; i++) {
12         if(i == 4 || i==2&&state)
13             continue;
14         ret += dfs(len-1, i==6, fp&&i == maxx); //对于这一题， 当这一位为6的时候， 下一位就会有限制
15     }
16     if(!fp)
17         return dp[len][state] = ret;
18     return ret;
19 }
20 int cal(int n) {
21     len = 0;
22     while(n) {
23         digit[++len] = n%10;
24         n/=10;
25     }
26     return dfs(len, false, true);
27 }
28 int main()
29 {
30     int a, b;
31     while(~scanf("%d%d", &a, &b)) {
32         if(a+b==0)
33             break;
34         mem1(dp);
35         printf("%d
", cal(b)-cal(a-1));
36     }
37 }