题目: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 ;
}
感谢您的阅读,生活愉快~