不要62（数位DP）

　杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。 
　杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。 
不吉利的数字为所有含有4或62的号码。例如： 
　62315　73418　88914 
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。 
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。 

 

Input

　输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。 

Output

　对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

 
Sample Input

1 100
0 0

Sample Output

80

题意：

求数字n到m中不含有“62”和“4”的数字个数。

思路：

数位DP，从最高位一位一位看，不重不漏

代码：

#include <stdio.h>
#include <string.h>

int a[100], dp[100][2];

int dfs(int cur, int limit, int rem)
                    //cur表示当前操作的是哪一位
                    //limit=1时小心超过n和m
                    //rem记录的是前一位是否为“6”
{
    if(cur==-1) return 1;
    else if(dp[cur][rem]!=-1&&limit==0) return dp[cur][rem];
                    //这种情况经过一次计算可以记下来，
                    //防止重复计算浪费时间
    else
    {
        int i, up, tem = 0;
        up = limit ? a[cur] : 9;   //确定最大可能的值
        for(i = 0; i <= up; i++)
        {
            if(i==4) continue;     //确保每一次操作都是正确的
            else if(i==2&&rem==1) continue;
            else tem += dfs(cur-1, limit==1&&i==up, i==6);
        }
        if(limit==0) dp[cur][rem] = tem;
        return tem;
    }
}

int solve(int x)
{
    memset(dp, -1, sizeof(dp));
    int cur = 0, re;
    while(x>0)
    {
        a[cur++] = x % 10;
        x /= 10;
    }
    re = dfs(cur-1, 1, 0);
    return re;
}

int main()
{
    int n, m, re;
    while(~scanf("%d %d", &n, &m))
    {
        if(!n&&!m) break;
        re = solve(m) - solve(n-1);
        printf("%d
", re);
    }
    return 0;
}