题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089
题目大意：给你一个区间[L, R]，让你求这个区间里满足没有连续62并且没有4的数字个数。

入门的数位dp：

优化：memse放在多样例外面。
因为这个记忆化与输入的数字无关， 是每个数自身的属性， 例如100里面的不要62的数有多少个是固定的，并且我们当前是没有上界限制的， mt=0。

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

int a[20];
LL dp[20][2];

//pos:当前的位 pre：上一位的数字 st：上一位是否为6 mt:前面的数位是否达到上界
LL dfs(int pos, int pre, int st, bool mt)
{
    //递归边界
    if(pos==-1)
    {
        return 1;
    }
    
    //记忆化搜索
    if(!mt&&dp[pos][st]!=-1)
    {
        return dp[pos][st];
    }
    
    //这一位的范围
    int Len=mt?a[pos]:9;
    
    //保存结果
    LL ans=0;
    for(int i=0;i<=Len;i++)
    {
        //限制条件
        if(pre==6&&i==2||i==4)
        {
            continue;
        }
        //继续递归
        ans+=dfs(pos-1, i, i==6, mt&&i==a[pos]);
    }

    if(!mt)
    {
        dp[pos][st]=ans;
    }

    return ans;

}

LL solve(LL x)
{
    //数位分离
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }

    return dfs(pos-1, -1, 0, true);
}

int main()
{
    int L, R;
    memset(dp, -1, sizeof(dp));
    while(scanf("%d%d",&L,&R),!(L==0&&R==0))
    {
        cout<<solve(R)-solve(L-1)<<endl;
    }

    return 0;
}