题目链接
题面
图片说明
简单的数位DP板子题

#include<bits/stdc++.h>
using namespace std;
int n,m;
int len=0;
int a[100];
int dp[100][2];
void work(int x){
    while(x!=0){
        a[++len]=x%10;
        x=x/10;
    } 
    return ;
}
int dfs(int lenn,bool is6,bool is_max){
    if(!lenn) return 1;
    if(!is_max&&dp[lenn][is6]!=-1) return dp[lenn][is6];
    int ans=0;
    int mm=is_max?a[lenn]:9;
    for(int i=0;i<=mm;i++){
        if(i==4) continue;
        if(is6&&i==2) continue;
        ans+=dfs(lenn-1,i==6,is_max&&i==mm);
    }
    if(!is_max) dp[lenn][is6]=ans;
    return ans;
}
int main(){
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        memset(a,0,sizeof(a));
        memset(dp,-1,sizeof(dp));
        int ans1=0,ans2=0;
        len=0;
        work(m);
        ans1=dfs(len,false,true);
        len=0;
        memset(a,0,sizeof(a));
        memset(dp,-1,sizeof(dp));
        work(n-1);
        ans2=dfs(len,false,true);
        //cout<<"ans1="<<ans1<<" ans2="<<ans2<<endl;
        cout<<(ans1-ans2)<<endl;
    }
    return 0;
}