HDU咋还在维护捏[脑壳疼]（↓HDU进不去只能拿自家的题面来了）
Description
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。
Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
Sample Input
Sample Output
因为自家oj测试数据比较弱，所以第一次写的时候hin快乐地暴力过了。等后续HDU又看见了这题，于是天晴了雨停了我又觉得行了，然后HDU快快乐乐T了一发……then快快乐乐百度，发现了快快乐乐的数位dp
数位dp，一种计数用的dp，一般用来统计一个区间[l,r]内满足一些条件数的个数。
顾名思义就是按位dp
所以首先将数字按位（注意进制吖）拆分出来放入dig数组中
这部分主要代码如下：
while (v) {
dig[cnt++] = v % 10; //拆分每位 从后往前放入数组中
v /= 10;
}
ll dfs(int pos, int six, int flag) { //pos标记第几位，six标记前一位是否为6（如果是6，six=1；否则six=0），flag标记前几位是否都与上限相应位数字相同（比如说上限为1234，当前三位为123时，flag=1，作用为告诉第四位不可超过4
if (pos < 0) return 1; //位dfs完了返回
ll ans = 0;
if (dp[pos][six][flag] != -1) return dp[pos][six][flag]; //记忆化
for (int i = 0; i <= 9; i++) {
if (flag == 1 && i > dig[pos]) break; //判断上限
if (i == 4) continue; //如果当前位是4，跳过
if (six && i == 2) continue; //如果前一位是6，并且当前位是2，则为62，跳过该数迭代
ans += dfs(pos - 1, i == 6, flag && i == dig[pos]); //如果目前为止的几位都符合题目要求，则继续dfs下一位，并判断当前位数是否为6，以及判断上限
}
return dp[pos][six][flag] = ans; //都dfs完了就是答案啦
}
1 #include<bits/stdc++.h> 2 #define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 3 using namespace std; 4 typedef long long ll; 5 ll dp[10][2][2]; //dp[位数][判断前一位是否为6][是否到达当前位上限] 6 int dig[10]; 7 8 ll dfs(int pos, int six, int flag) { 9 if (pos < 0) return 1; //为啥不是return 0呢（虽然return 0 答案forever就是0了
10 ll ans = 0; 11 if (dp[pos][six][flag] != -1) return dp[pos][six][flag]; //记忆化 12 for (int i = 0; i <= 9; i++) { 13 if (flag == 1 && i > dig[pos]) break; //判断上限 14 if (i == 4) continue; 15 if (six && i == 2) continue; 16 ans += dfs(pos - 1, i == 6, flag && i == dig[pos]); //递归 17 } 18 return dp[pos][six][flag] = ans; 19 } 20 21 ll solve(ll v) { 22 memset(dp, -1, sizeof(dp)); 23 if (v < 0) return 0; 24 int cnt = 0; 25 while (v) { 26 dig[cnt++] = v % 10; //拆分每位 从后往前放入数组中 27 v /= 10; 28 } 29 return dfs(cnt - 1, 0, 1); //从最高位开始递归 30 } 31 32 int main() { 33 O_O; 34 ll n, m; 35 while (cin >> n >> m) { 36 if (!n && !m) break; 37 cout << solve(m) - solve(n-1)<<"\n"; 38 } 39 return 0; 40 }
原文：https://www.cnblogs.com/GJnghost/p/11628431.html