算法复习——数位dp（不要62HUD2089）-白红宇

题目

题目描述

杭州人称那些傻乎乎粘嗒嗒的人为 62（音：laoer）。

杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有 4 或 62 的号码。例如：62315 73418 88914 都属于不吉利号码。但是，61152 虽然含有 6 和 2，但不是 62 连号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

输入格式

输入一行，一个空格隔开的两个整数 n 和 m（0<n≤m<100000000）。

输出格式

对于给出的整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

样例数据 1

输入　 []

1 100

输出

80

题解：

数位DP裸题，注意记忆化DFS，pos表示搜索到的位置，pre表示搜索到的该位置前枚举的数，limit表示pre是否已经到达最大值

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;int dp[15][15][2],bit[15],len;inline void trans(int x){ memset(dp,-1,sizeof(dp)); memset(bit,0,sizeof(bit)); len=0; int temp=x; while(temp) { len++; temp/=10; } temp=x; for(int i=len;i>=1;i--) { bit[i]=temp%10; temp/=10; }}inline int Dfs(int pos,int pre,bool ifend){ if(pos==len+1) return 1; if(dp[pos][pre][ifend]!=-1) return dp[pos][pre][ifend]; int end; end=(ifend?bit[pos]:9); int ans=0; for(int i=0;i<=end;i++) { if((pre==6&&i==2)||i==4) continue; ans+=Dfs(pos+1,i,ifend&&i==end); } return dp[pos][pre][ifend]=ans;}int main(){ //freopen("a.in","r",stdin); int n,m; scanf("%d%d",&n,&m); trans(n-1); int temp1=Dfs(1,0,1); trans(m); int temp2=Dfs(1,0,1); cout<
               
                <