Input
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。
Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
Sample Input
1 100 0 0
Sample Output
80
数位dp之前听说了一下，今天终于学到了，原来就是根据数字的位数（千位、十位、百位等）做dp，然后就是求某个区间上符合某条件的数的个数，一般就用数位dp来解决，毕竟暴力几乎T。
对于上面这道题，求的是区间上不含有4和62的数字的个数，直接求出0到这两个数直接符合条件的数字，然后做差就行了。
第一种dp方法：
用dp[i][j]表示第i位上为j-1到j的所有数字中符合条件的数字的个数。比如dp[2][1]就是0~10中符合条件数字的个数，dp[3][2]就是100~200之间符合条件的数字的个数。
用状态转移方程来表示就是：
0, j=4;
dp[i][j]= ∑ dp[i-1][k],(0<=k<=9), j!=6;
∑ dp[i-1][k],(0<=k<=9&&k!=2), j=6;
然后在把给出的数字XnXn-1……X1(这是一个数字，xi表示第i位上的数)分成Xn*10^(n-1)+X(n-1)*10^(n-2)+……+X1,把每一位上符合条件的数字求出来就好了。
代码：
1 #include<iostream> 2 using namespace std; 3 int n,m,dp[8][10]; 4 void init() 5 { 6 dp[0][0]=1; 7 for(int i=1;i<=9;i++) 8 { 9 for(int j=0;j<=9;j++) 10 { 11 if(j==4)dp[i][j]=0; 12 else { 13 for(int k=0;k<=9;k++) 14 { 15 if(j==6&&k==2)continue; 16 dp[i][j]+=dp[i-1][k]; 17 } 18 } 19 } 20 } 21 } 22 int find(int x) 23 { 24 int ans=0,cnt=0,p[10]; 25 while(x) 26 { 27 p[++cnt]=x%10; 28 x/=10; 29 } 30 p[cnt+1]=0; 31 for(int i=cnt;i>=1;i--) 32 { 33 for(int j=0;j<p[i];j++) 34 { 35 if(j==4||(j==2&&p[i+1]==6))continue; 36 ans+=dp[i][j]; 37 } 38 if(p[i]==4||(p[i]==2&&p[i+1]==6))break; 39 } 40 return ans; 41 } 42 int main() 43 { 44 init(); 45 while(cin>>n>>m&&(n||m))cout<<find(m+1)-find(n)<<endl; 46 }
不明白find函数的建议用笔模拟一遍。还有就是结果是f(m+1)-f(n)是为什么？这是因为f(m)求的是[0，m)区间上的个数，并没有把m这个数算进去，f(m+1)-f(n)得到的就是[n,m]上的答案啦。
第二种dp方法：
这个方法用到了dfs和记忆化搜索，还好在这之前学了记忆化搜索和dfs，不然不可能搞懂这个鬼东西的。
我是看这大佬
先贴上代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[8],f[10][2]; 4 int dfs(int d,bool is6,bool limit) 5 { 6 if(d==0)return 1; 7 if(!limit&&f[d][is6]!=-1)return f[d][is6]; 8 int cur=0,end=(limit?a[d]:9); 9 for(int i=0;i<=end;i++) 10 { 11 if((is6&&i==2)||i==4)continue; 12 cur+=dfs(d-1,i==6,limit&&i==end); 13 } 14 if(!limit)f[d][is6]=cur; 15 return cur; 16 } 17 int solve(int x) 18 { 19 memset(a,0,sizeof(a)); 20 int cnt=0; 21 if(!x)a[++cnt]=0; 22 while(x){a[++cnt]=x%10;x/=10;} 23 return dfs(cnt,0,1); 24 } 25 int main() 26 { 27 memset(f,-1,sizeof(f)); 28 int n,m; 29 while(cin>>n>>m&&(n||m)) 30 { 31 cout<<solve(m)-solve(n-1)<<endl; 32 } 33 return 0; 34 }
1，先看 dfs(int d，bool is6，bool limit) 这里的d是指数字的第几位，is6是判断这个位置上的数字是不是6，limit用来判断这个位置上的数字有没有达到最大
2，f[d][is6]是用来记忆化搜索的，记忆第d位是6和不是6的数的个数，不用每次都重复去算，可以加快dfs的速度
3，第8行是判断上界用的，如果这一位数已经到了上界，那么就从0最大放到a[d]，否则一直放到9
4，因为solve(m)求的是[0，m]区间，所以答案应该是solve(m)-solve(n-1)
原文：https://www.cnblogs.com/hailin545/p/12271544.html