传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2089

题目大意：
告诉你一个范围 n ~ m，例如 200 ~ 3000, 问你在这个范围内，不包含 62 ，也不包含 4 的数有多少个。
例如 1062、1620、401 等都是不满足要求的，因为存在 62 或者 4，但像 1602 是可以的，因为不存在 62（要求必须连续）。

解题思路：
数位DP简单题，对于 62，我们在 dfs() 函数中用一个参数来表示前一个位是否是 6，当前一位是 6 并且当前位是 2，就跳过不要了；对于 4，因为就一个数，所以也不用去记忆化，直接遇到就跳过就行，最后统计数目。

通过代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 10
using namespace std;
int a[MAX];
int n, m;
int dp[MAX][2];
int dfs(int pos, int sta, bool islimit) // sta = 1 表示前一位是 6
{
    if (pos == 0)
        return 1;
    if (!islimit && dp[pos][sta] != -1)
        return dp[pos][sta];
    int up = islimit ? a[pos] : 9;
    int cnt = 0;
    for (int i = 0; i <= up; ++i)
    {
        if (i == 4 || (sta && i == 2))
            continue;
        cnt += dfs(pos - 1, i == 6, islimit && i == a[pos]);
    }
    if (!islimit)
        dp[pos][sta] = cnt;
    return cnt;
}
int solve(int num)
{
    int pos = 0;
    while (num)
    {
        a[++pos] = num % 10;
        num /= 10;
    }
    return dfs(pos, 0, true);
}
int main(void)
{
    memset(dp, -1, sizeof(dp)); // 范围的改变并不会导致记忆的内容失效，因为是否符合包含62或4这个条件，是数本身的属性，与范围无关，所以对于所有的测试数据，初始化一次就可以了。
    while (scanf("%d%d", &n, &m) && m)
        printf("%d\n", solve(m) - solve(n - 1));
}