HDU 2089 不要62（数位dp模板题）

http://acm.hdu.edu.cn/showproblem.php?pid=2089

题意：
求区间内不包含4和连续62的数的个数。

思路：

简单的数位dp模板题。给大家推荐一个好的讲解博客。http://blog.csdn.net/mosquito_zm/article/details/75226543

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 const int INF = 0x3f3f3f3f;
14 const int maxn=100000+5;
15 
16 int l,r;
17 int dp[maxn][2];
18 int dig[30];
19 
20 int dfs(int pos, int pre, int state, int limit)
21 {
22     if(pos==-1)  return 1;
23     if(!limit && dp[pos][state]!=-1)  return dp[pos][state];
24     int up=limit?dig[pos]:9;
25     int tmp=0;
26     for(int i=0;i<=up;i++)
27     {
28         if(i==4) continue;
29         if(pre==6 && i==2)  continue;
30         tmp+=dfs(pos-1,i,i==6,limit&&i==dig[pos]);
31     }
32     if(!limit)  dp[pos][state]=tmp;
33     return tmp;
34 }
35 
36 int solve(int x)
37 {
38     int pos=0;
39     while(x)
40     {
41         dig[pos++]=x%10;
42         x/=10;
43     }
44     return dfs(pos-1,-1,0,1);
45 }
46 
47 int main()
48 {
49     //freopen("in.txt","r",stdin);
50     while(~scanf("%d%d",&l,&r))
51     {
52         if(l==0 && r==0)  break;
53         memset(dp,-1,sizeof(dp));
54         int ans=solve(r)-solve(l-1);
55         cout<<ans<<endl;
56     }
57     return 0;
58 }