不要62                   

杭州人稱那些傻乎乎粘嗒嗒的人為62（音：laoer）。 杭州交通管理局經(jīng)常會擴(kuò)充一些的士車牌照，新近出來一個好消息，以后上牌照，不再含有不吉利的數(shù)字了，這樣一來，就可以消除個別的士司機(jī)和乘客的心理障礙，更安全地服務(wù)大眾。不吉利的數(shù)字為所有含有4或62的號碼。例如： 62315 73418 88914 都屬于不吉利號碼。但是，61152雖然含有6和2，但不是62連號，所以不屬于不吉利數(shù)字之列。 你的任務(wù)是，對于每次給出的一個牌照區(qū)間號，推斷出交管局今次又要實(shí)際上給多少輛新的士車上牌照了。

1 1000 0Sample Output
80
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int dp[10][2];int a[10];int dfs(int pos,bool we,int last){    if(!pos) return 1;    if(!last&&dp[pos][we]!=-1) return dp[pos][we];    int len=last?a[pos]:9;    int ans=0;    for(int i=0; i<=len; i++)    {        if(i==4||we&&i==2) continue;//如果是2并且we=1，說明62湊成了，有62或者4則不計(jì)，省略過去        ans+=dfs(pos-1,i==6,last&&(i==len));//上一個為6則we標(biāo)記為1，說明6出現(xiàn)了    }    if(!last) dp[pos][we]=ans;    return ans;}int cal(int n){    int len=0;    while(n)    {        a[++len]=n%10;        n/=10;    }    return dfs(len,0,1);}int main(){    int l,r;    memset(dp,-1,sizeof(dp));    while(cin>>l>>r)    {        if(l==0&&r==0) break;        cout<<cal(r)-cal(l-1)<<endl;    }    return 0;}