数位DP - HDU 2089

///HDU 2089

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int digit[20];
LL dp[20][2];//当前数位 含有6时，区间内有多少数 没有62 当前数位不是6时 区间内有多少数 没有62 ！！！

///if4=>status(状态)是否是6
LL dfs(int len,bool if6,bool limit)
{
    //len表示当前位 ！！   if6表示len的上一位是否是6！！   limit表示当前位的最大约束 ！！
    if(len==0) return 1ll;//个位数时  满足条件的个数仅为一！
    if(!limit && dp[len][if6]) return dp[len][if6];
    //当前数位的数 没有到达上界，且统计过  则直接返回！！
    //典型的记忆化 的语句！！

    LL cnt=0,up_bound=(limit?digit[len]:9);//当前位  上界的约束！！
    for(int i=0;i<=up_bound;++i){
        if(if6 && i==2)///=>找到一个49
            continue;
        if(i==4) continue;//剪枝
        cnt+=dfs(len-1,i==6,limit&&i==up_bound);
        /*为下一位设上限 ！！*/
    }
    if(!limit) dp[len][if6]=cnt;
    return cnt;
//如果这一位 不含上界则作为完整的数 可以记录下来 ！！
//统计在数位上  下次dfs时以便遇见直接返回！！

}
///统计的是没有62的个数
LL solve(LL num){
    int k=0;
    while(num){
        digit[++k]=num%10;
        num/=10;
    }
    return dfs(k,false,true);//dfs记忆爆搜
}

int main(){

    LL N,M;
    while(cin>>N>>M && N+M){

    //注意0 0 的特判  当n=0时，n-1=-1，这时solve（-1）代入跑dfs，得出的结果就还真是0
    //所以我感觉这套板子的强度很大！！！   满足卡特判的活！！！
    //精髓在 ！！！卡特判！！！
        cout<<solve(M)-solve(N-1)<<endl;
    }
    return 0;
}