题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2089
数位dp的模板题，统计一个区间内不含62的数字个数和不含4的数字个数，直接拿数位dp的板子敲就行，注意每次调用solve函数要初始化dp数组，否则之前调用的时候dp数组可能被记录过。
AC代码：
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
using namespace std;
const int maxn = 10;
int dp[maxn][3][3],nums[maxn];//dp[i][j][k] i表示当前第几位,j表示上一位是否为6，k表示是否受上一位限制
int dfs(int pos,bool pre,bool limit){
if(pos == 0) return 1; //搜索到第0位，返回
if(dp[pos][pre][limit] != -1) return dp[pos][pre][limit];//记忆化，如果搜索过就返回
int up = limit?nums[pos]:9;//判断受上一位影响就
int res = 0;
for(int i = 0;i<=up;i++){
if(i == 4 || (pre && i == 2)) continue;
res += dfs(pos-1,i == 6,limit && i == up);//统计满足条件的个数，递归
}
dp[pos][pre][limit] = res;
return res;
}
int solve(int up){
int k = 1;
while(up){//数位分离
nums[k] = up%10;
k++;
up/=10;
}
return dfs(k-1,0,1);
}
int main(){
int n,m;
while(scanf ("%d%d", &n, &m) != EOF){
if(n == 0 && m == 0) break;
memset(dp,-1,sizeof(dp));
int t1 = solve(m);
memset(dp,-1,sizeof(dp));
int t2 = solve(n-1);
printf("%d\n",t1-t2);
}
return 0;
}