HDU - 3555 Bomb

Posted on | In , ,

思路
现在发现自己的dp实在是烂，决定把kuangbin专题下的dp都刷一遍。

数位dp的题通常会让你求在[l,r]区间中符合条件的数，比如这道题是带有‘49’的数。为了求解，我们使用一个二位的dp数组，第一维是长度，第二维是这位的数字（1-9）。首先我们要初始化dp数组，然后再判断小于给定n的数有多少个不包括49.这是一个二重循环，第一重循环是当前位数，第二重是1-digit[i]-1。我们可以理解为对一个数2345，我们先固定首位2，计算2000-2299，然后2300-2339这样递推，然后注意下当前数包含49的话可以直接退出循环，因为后面的数都不符合条件（比如4949，算完前两位就不用算了）。
代码

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
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <cctype>
#include <sstream>
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1+1)

using namespace std;
ll dp[45][10];
void init() {
	//in order to init dp[1][i]=1
	dp[0][0] = 1;
	for (int i = 1;i <= 40;i++) {
		for (int j = 0;j <= 9;j++) {
			for (int k = 0;k <= 9;k++) {
				if (!(j == 4 && k == 9))dp[i][j] += dp[i - 1][k];
			}
		}
	}
}
ll solve(ll n) {
	int digit[45];
	ll x = n, j = 0, ans = 0;
	while (x) {
		digit[j++] = x % 10;
		x /= 10;
	}
	reverse(digit, digit + j);
	for (int i = 0;i<j;i++) {
		for (int k = 0;k<digit[i];k++) {
			if(!(digit[i-1]==4&&k==9))ans += dp[j - i][k];
		}
		if (digit[i - 1] == 4 && digit[i] == 9)break;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int t;
	ll n;
	ms(dp, 0);
	init();
	cin >> t;
	while (t--) {
		cin >> n;
		cout << n + 1 - solve(n + 1) << "\n";
	}
	return 0;
}