废话不多说，直接上题：
1589：不要 62
时间限制: 1000 ms 内存限制: 524288 KB
提交数: 105 通过数: 67
【题目描述】
原题来自：HDU 2089
杭州人称那些傻乎乎粘嗒嗒的人为 62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有 4 或 62 的号码。例如：62315,73418,8891462315,73418,88914 都属于不吉利号码。但是，61152 虽然含有 6 和 2，但不是 62 连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今后又要实际上给多少辆新的士车上牌照了。
【输入】
输入的都是整数对 n,m，如果遇到都是 0 的整数对，则输入结束。
【输出】
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
【输入样例】
1 100 0 0
【输出样例】
80
【提示】
数据范围与提示：
对于全部数据，0<n≤m<107 。
【来源】
这道题乍一看挺简单，但是看一眼心态就崩了。107，而且还是多次输出，一看就是要预处理，像这种要预处理的而且和数位有关的，使我们会想到数位动态规划。
小编最开始的想法很简单，f[i]表示0~i之间的合法个数，那么就有f[i]=f[i-1]+(i==合法)；（伪代码），那么答案就是f[m]-f[n-1]，似乎是区间动态规划的方法。但是时间太慢了，小编也觉得不太可能。
这是小编想到的状态，实在想不到和数位有关的方法了。看了看大佬的博客才发现状态原来可以这样设计：用f[i][j]表示以j开头的i位数的合法个数。
那么就很清晰了，就有f[i][j]=sum{f[i-1][k]}，其中k！=4，j！=4，！（k==2&&j==6），举个栗子：比如说f[3][1]=f[2][0]+f[2][1]+f[2][2]+f[2][3]+f[2][5]+f[2][6]+f[2][7]+f[2][8]+f[2][9]。
那么剩下的问题就是怎么处理区间[n,m]，把它分为[0,n]和[0,m+1]（知道你会说什么，这和后面的算法有关）。
先不说n和m，假设现在要统计0~71806291的区间，那么我们就可以遍历各个数位i，同时枚举各数位数字j，如果合法，那么就把答案加上f[i][j]就可以了，如果发生了这样的情况：题目中的数字不合法，那么就加上f[i][j]后退出循环，因为后面的都计过了。比如说6291，先到了6，加上5000个数的合法个数，到了2会加上2000个数的合法个数，然后退出循环，就会发现前6200的合法个数都加上了，而后面的就不加了，因为这是建立在6200的基础上的，一定不合法。
好了，详见注释，代码如下：
1 #include<iostream> 2 using namespace std; 3 int n,m,f[1000][1000]; 4 int calc(int x)//计算0~x区间内合法个数 5 { 6 int s[1000]={0},cnt=0,ans=0; 7 while(x)//分解数位 8 { 9 s[++cnt]=x%10; 10 x/=10; 11 } 12 for(int i=cnt;i>=1;i--) 13 { 14 for(int j=0;j<=s[i]-1;j++) //因为后面的数不能超过，所以只能到s[i]-1 15 if(!(j==4||(j==2&&s[i+1]==6))) ans+=f[i][j];//合法就加上 16 if(s[i]==4||(s[i]==2&&s[i+1]==6)) break;//数字中不合法就退出循环 17 } 18 return ans; 19 } 20 int main() 21 { 22 f[0][0]=1; 23 for(int i=1;i<=7;i++)//预处理 24 for(int j=0;j<=9;j++) 25 for(int k=0;k<=9;k++) 26 if(j!=4&&!(j==6&&k==2)) f[i][j]+=f[i-1][k]; 27 while(1) 28 { 29 cin>>n>>m; 30 if(n==0&&m==0) break; 31 cout<<calc(m+1)-calc(n)<<endl; 32 } 33 return 0; 34 }