最近在学数位DP

应该是入门题吧

设\( dp[i][0/1] \)表示到第\( i \)位时，前一位是否是6的满足条件的数的个数

然后就是套路

注意\( limit \)的限制条件以及转移时候信息的记录，不能遗漏信息

代码写的记忆化搜索

#include 
     
      #include 
      
       #include 
       
        using namespace std;int dp[100][2],a[100];int dfs(int pos,int pre,int limit,int state){  if(pos==-1)    return 1;  if(!limit&&dp[pos][state]!=-1)    return dp[pos][state];  int up = limit?a[pos]:9;  int mid=0;  for(int i=0;i<=up;i++){    if(i==4)      continue;    if(pre==6&&i==2){      continue;    }    mid+=dfs(pos-1,i,limit&&i==a[pos],i==6);  }  if(!limit)    dp[pos][state]=mid;  return mid;}int solve(int x){  int con=0;  memset(dp,-1,sizeof(dp));  memset(a,0,sizeof(a));  while(x){    a[con]=x%10;    x/=10;    con++;  }  return dfs(con,-1,true,false);}int main(){  int l,r;  while(scanf("%d %d",&l,&r)==2&&l!=0&&r!=0)    printf("%d\n",solve(r)-solve(l-1));  return 0;}