学步园

和49那题是一样的，就是判断的时候会多一两个判断，然后就是要注意每次算出来的结果都是在小于n的情况下成立的。

#include <stdio.h>
#include <string.h>
#define ll __int64
ll dp[25][3];
ll solve(ll n)
{
    ll i,j,k;
    j=n;
    int top=0;
    ll que[25];
    memset(que,0,sizeof(que));
    while(j)
    {
        que[++top]=j%10;
        j/=10;
    }
    k=0;
    int flag=0;
  //  for(i=1;i<=top;i++) printf("**%d",que[i]);printf("\n");
    //int que[25];
  //  memset(que,0,sizeof(que));
    for(i=top;i>=1;i--)
    {
        k+=dp[i-1][2]*que[i];
        if(flag) k+=dp[i-1][0]*que[i];
        else
        {
            if(que[i]>6) k+=dp[i-1][1];
            if(que[i]>4) k+=dp[i-1][0];
            if(que[i+1]==6&&que[i]>2) k+=dp[i][1];
        }
        if(que[i+1]==6&&que[i]==2||que[i]==4) flag=1;
    }
    return k;
}
int main()
{
    ll n,m;
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;          //这里注意初始化
    for(int i=1;i<=20;i++)
    {
        dp[i][0]=dp[i-1][0]*9-dp[i-1][1];
        dp[i][1]=dp[i-1][0];
        dp[i][2]=dp[i-1][2]*10+dp[i-1][1]+dp[i-1][0];
    }
    while(scanf("%I64d%I64d",&n,&m)!=EOF&&n+m)
    {
        ll ans,tmp;
        ans=solve(n);
        tmp=solve(m+1);    //注意这里放的是m
      //  printf("**%I64d  %I64d\n",ans,tmp);
        printf("%I64d\n",m-n+1-tmp+ans);
    }
    return 0;
}

**********************************************

用DFS写的，，，其实看过很多dfs的DP，然后平生最恨这样写！！。。。。。但是自己写了之后其实感觉还不错。。。。。

state表示之前是否有6，fp大概表示是否达到了原值的那个数字。

#include <stdio.h>
#include <string.h>
#define ll __int64
ll que[30];
ll dp[30][2];
ll dfs(int len,int state,int fp)
{
    if(!len) return 1;
    if(dp[len][state]!=-1&&!fp) return dp[len][state];
    int i,j,k;
    ll ret=0;
    int fmax=fp?que[len]:9;
    for(i=0;i<=fmax;i++)
    {
        if(i==4||i==2&&state) continue;
        ret+=dfs(len-1,i==6,fp&&i==fmax);
    }
    if(!fp) dp[len][state]=ret;
    return ret;
}
ll solve(ll n)
{
    ll i,j,k;
    j=n;
    k=0;
    while(j)
    {
        que[++k]=j%10;
        j/=10;
    }
    return dfs(k,0,1);
}
int main()
{
    ll n,m;
    memset(dp,-1,sizeof(dp));
    while(scanf("%I64d%I64d",&n,&m)!=EOF&&n+m)
    {
        ll a,b;
        a=solve(n-1);
        b=solve(m);
        printf("%I64d\n",b-a);
    }
    return 0;
}