题面
大秦为你打开题目传送门
题目描述
请统计从 $1$ 到 $N$ 的整数中有多少个包含 $49$ 。
例如：49315， 734949418， 8449814都是包含 $49$ 的整数。
但是，41159虽然含有 $4$ 和 $9$ ，但不是 $49$ 连号，所以不属于统计范围。
思路
数位DP模板题。我们用 $\tt mask$ 表示当前格子的状态。
- 啥也没有
- 以四结尾
- 有 $49$ 。
这样子的话就可以正常的递归求解了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
ll n;
int a[110];
int len;
ll dp[110][4];
inline void Input() {
read(n);
}
ll Dfs(int len, int mask, int limit) {
if(len == 0) {
return mask == 2;
}
if(!limit && dp[len][mask] != -1) {
return dp[len][mask];
}
int mx = limit ? a[len] : 9;
ll ans = 0;
for(int i = 0; i <= mx; i++) {
int nwmk = 0;
if(i == 4 && (mask == 0 || mask == 1)) nwmk = 1;
else if(i == 9 && mask == 1) nwmk = 2;
else if(mask == 2) nwmk = 2;
ans += Dfs(len - 1, nwmk, limit && i == mx);
}
if(!limit) dp[len][mask] = ans;
return ans;
}
inline void Work() {
memset(dp, -1, sizeof(dp));
while(n) {
a[++len] = n % 10;
n /= 10;
}
printf("%lld\n", Dfs(len, 0, 1));
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
