首页 > 代码库 > HDU 2089 不要62 数位DP

HDU 2089 不要62 数位DP

题目思路:

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

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

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

 

技术分享
 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 #include<stdio.h> 6 #include<stdlib.h> 7 #include<queue> 8 #include<math.h> 9 #include<map>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 }
View Code

 

HDU 2089 不要62 数位DP