HDU 2089 不要62 数位DP-白红宇

HDU 2089 不要62 数位DP

阅读量：4353 次

发布时间：2019-06-07

本文共 1333 字，大约阅读时间需要 4 分钟。

题目思路：

dp[][0]存放不含不吉利数字的个数

dp[][1]存放上一位为6且不含不吉利数字的个数

dp[][2]存放含不吉利数字的个数

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              10 #define INF 0x3f3f3f3f11 #define MAX 100000512 #define Temp 100000000013 14 using namespace std;15 16 long long dp[20][3];17 int num[20];18 19 long long dfs(int pos,int status,int limit)20 {21 if(pos<0)22 return status==2;//若含不吉利数字计数器加123 if(!limit && dp[pos][status]!=-1)24 return dp[pos][status];25 long long ans=0;26 int len=limit?num[pos]:9;27 for(int i=0;i<=len;i++)28 {29 if(i==4 || status==2 || (i==2 && status==1))30 ans+=dfs(pos-1,2,i==len&&limit);31 else if(i==6)32 ans+=dfs(pos-1,1,i==len&&limit);33 else34 ans+=dfs(pos-1,0,i==len&&limit);35 }36 if(!limit)37 dp[pos][status]=ans;38 return ans;39 }40 41 long long solve(long long a)42 {43 int len=0;44 memset(num,-1,sizeof(num));45 memset(dp,-1,sizeof(dp));46 while(a)47 {48 num[len++]=a%10;49 a/=10;50 }51 return dfs(len-1,0,1);52 }53 54 int main()55 {56 long long a,b;57 while(scanf("%lld%lld",&a,&b),a+b)58 {59 long long ans=solve(b)-solve(a-1);60 printf("%I64d\n",b-a+1-ans);61 }62 return 0;63 }