不要62 hdu 2089 dfs记忆化搜索

时间:2021-06-02 21:01:02

题目: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 ;
}

感谢您的阅读,生活愉快~