题目链接
题面
简单的数位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; }