hdu 2089 不要62

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089

题意：给出一个区间[l,r]，求满足一个数的数位上没有连着62这个数字串的条件的个数。

解法：数位DP的入门题。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define inf 0x7fffffff
 8 #define exp 1e-10
 9 #define PI 3.141592654
10 using namespace std;
11 int digit[8];
12 int dp[8][2];
13 int dfs(int len,bool state,bool fp)
14 {
15     if (!len) return 1;
16     if (!fp && dp[len][state]!=-1) return dp[len][state];
17     int ret=0;
18     int fpmax= fp ? digit[len] : 9 ;
19     for (int i=0 ;i<=fpmax ;i++)
20     {
21         if (i==4 || (state && i==2)) continue;
22         ret += dfs(len-1,i==6,fp && i==fpmax);
23     }
24     if (!fp) return dp[len][state]=ret;
25     return ret;
26 }
27 int f(int n)
28 {
29     int len=0;
30     while (n)
31     {
32         digit[++len]=n%10;
33         n /= 10;
34     }
35     return dfs(len,false,true);
36 }
37 int main()
38 {
39     int n,m;
40     while (cin>>n>>m)
41     {
42         if (!n && !m) break;
43         memset(dp,-1,sizeof(dp));
44         printf("%d
",f(m)-f(n-1));
45     }
46     return 0;
47 }