http://acm.hdu.edu.cn/showproblem.php?pid=2089

HDU2089不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 45764    Accepted Submission(s): 17240 Problem Description 杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。 杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。 不吉利的数字为所有含有4或62的号码。例如： 62315 73418 88914 都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。 你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。   Input 输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。   Output 对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。   Sample Input 1 100 0 0   Sample Output 80 【解析】：

所谓的数位dp解决，其实就是记忆化搜索。用数组dp记忆。

把十进制数分解每一位，存入数组a，然后dfs，深度为位数。（从高位数第几位）

dfs第一层，可以放的数字枚举，然后递归进入第二层（即第二位）计算第二层放数字i是否符合题意。

如果这个dfs不加记忆化，直接dfs过程中判断是否满足题意，其时间复杂度和for循环对每个数进行检查是否满足题意是差不多的。记忆化的精髓可以画个图更直观的看出来。

看图中pos=top-1的那一层，其实0节点，和1节点底下的符合条件的数量是一样的。

所以记忆化就是，在计算完0节点底下的那块搜索之后，就用dp存下这一层底下的数目，当再计算进入1节点底下的时候，直接加dp就行，不用再往底下递归，所以记忆化搜索大大降低了时间复杂度

有一个上界限制需要把握好。图中绿线圈起来的就是上界，不能超过4 1...这个数字。

控制方法是，加一个limit变量跟随递归，记录上一层的那个节点是不是边界，如果是，那么这一层选择数字就得小心了。不能超过上限。

此题的限制条件是上一位是6的时候，当前位不能为2。导致节点6下面的数量，和其他节点下面的数量不一致，所以记忆化需要记忆6和不是6的分开

还有边界上的搜索路径也不能记忆，因为上界不一定。所以上图中第一层节点0,1,2,3是相等的记忆化即可。

【代码】：

#include <stdio.h> #include <string.h> #define mset(a,i) memset(a,i,sizeof(a)) #define S2(n,m) scanf("%d%d",&n,&m) int dp[9][2];//dp[i][sta]表示第i位，状态sta时的记忆。sta为上一位是否是6 int a[9]; int dfs(int pos,int sta,int limit) { if(pos==-1)return 1; if(!limit&&dp[pos][sta])return dp[pos][sta]; int up=limit?a[pos]:9; int ans=0; for(int i=0;i<=up;i++) { if(i==4||sta&&i==2)continue; ans+=dfs(pos-1,i==6,limit&&i==a[pos]); } if(!limit)dp[pos][sta]=ans; return ans; } int solve(int x) { int top=0; mset(dp,0); while(x) { a[top++]=x; x/=10; } return dfs(top-1,0,1); } int main() { int l,r; while(~S2(l,r),l) { printf("%d\n",solve(r)-solve(l-1)); } return 0; }