# 题目大意
给出 $\text{T}$ 个数，求 $[1,n]$ 中含 ‘49’ 的数的个数。
# 解题思路
求出不含 '49' 的数的个数，用总数减去就是答案。
数位 $DP$，用记忆化来做。
设 $dp[i][0]$ 表示 (这里按照从左往右数) 长度为 $i$ 并且最后一位不是 '4' 的数的个数。
设 $dp[i][1]$ 表示长度为 $i$ 并且最后一位是 '4' 的数的个数。
上面这两行看不懂可以先跳过去，是不是很神奇。
这样单说不好说。借助代码来说。具体的看代码里的注释。
# 放上代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
LL T, n, num[30], cnt, dp[
30][
2];
inline void span(LL x) {
//将数字张开分成一位一位
cnt =
0;
while (x !=
0) {
num[++cnt] = x %
10;
x /=
10;
} //cnt就是长度
}
inline LL dfs(int l,
bool flag,
bool limit) {
//枚举到了第l位，最高位是cnt
//flag表示前一位是否是4，limit表示枚举第l位是否存在限制
if(l ==
0)
return 1;
if(!limit && dp[l][flag])
return dp[l][flag];
//这里返回的原因是没有限制，所以这是一个通用的答案
LL ans =
0, mx = (limit ? num[l] :
9);
//这里这个mx是最大能枚举到几，如果这一位存在限制。
for(
int i=
0; i<=mx; i++
) {
if(flag && i ==
9)
//判断是否含有‘49’
continue;
ans += dfs(l-
1, i ==
4, i == mx &&
limit);
//如果这一位有限制并且现在枚举到的数正好达到最高限制，证明下一位也有限制
}
return limit ? ans : dp[l][flag] =
ans;
//如果没有限制就可以将这个通用的答案记录下来
}
int main() {
scanf("%lld", &
T);
while (T--
) {
memset(num, 0,
sizeof(num));
//这里记得要重置
scanf(
"%lld", &
n);
span(n);
printf("%lld\n", n-(dfs(cnt,
false,
true)-
1));
//这里为什么要-1？
//因为在上面的函数中找到的不含‘49’的数包括‘0’，但是最后统计的时候是不包括‘0’的
}
}
转载于:https://www.cnblogs.com/bljfy/p/9615108.html
