题目：http://acm.hdu.edu.cn/showproblem.php?pid=2089
题意：
给你两个数作为一个闭区间的端点，求出该区间中不包含数字4和62的数的个数
思路：
数位dp中的 dfs 记忆化搜索方法解。
模板：
int dfs(int i, int s, bool e) {
if (i==-) return s==target_s;
if (!e && f[i][s] != -) return f[i][s];
int res = ;
int u = e?num[i]:;
for (int d = first?:; d <= u; ++d)
res += dfs(i-, new_s(s, d), e&&d==u);
return e?res:f[i][s]=res;
}
f为记忆化数组 ；
i为当前处理串的第i位（权重表示法，也即后面剩下i+1位待填数）；
s为之前数字的状态（如果要求后面的数满足什么状态，也可以再记一个目标状态t之类，for的时候枚举下t）；
e表示之前的数是否是上界的前缀（即后面的数能否任意填）。
代码如下：
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int a, b, shu[], dp[][]; int dfs(int len, bool if6, bool shangxian)
{
if (len == ) return ;
if (!shangxian && dp[len][if6]) return dp[len][if6];
int cnt = , maxx = (shangxian ? shu[len] : );
for (int i = ; i <= maxx; i++)
{
if (if6 && i == || i == )
continue;
cnt += dfs(len - , i == , shangxian && i == maxx);
}
return shangxian ? cnt : dp[len][if6] = cnt;
} int solve(int x)
{
memset(shu, , sizeof(shu));
int k = ;
while (x)
{
shu[++k] = x % ;
x /= ;
}
return dfs(k, false, true);
} int main()
{
while (cin >> a >> b, a&&b)
cout << solve(b) - solve(a - ) << endl; return ;
}
感谢您的阅读，生活愉快~