[HDU2089]不要62 题解

数位dp.

设$dp(i,j)$为还差$i$位,上一位为$j$的方案数。

限制不能填4或者不能填相邻的62就完事了。

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
/**
* @Author: Mingyu Li
* @Date: 2019-03-14T13:44:58+08:00
* @Email: class11limingyu@126.com
* @Filename: HDU2089.cpp
* @Last modified by: Mingyu Li
* @Last modified time: 2019-03-14T14:02:19+08:00
*/

#include <bits/stdc++.h>
#define Go(i , x , y) for(register int i = x; i <= y; i++)
#define God(i , y , x) for(register int i = y; i >= x; i--)
typedef long long LL;
template < typename T > void sc(T& t) {
char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();}
while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x;
}
template < typename T , typename... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);}

LL dp[20][11] , d[20];

// dp(i,j) : 还差i位 上一位是x,接下来不同的数的个数

LL f(LL i , LL j) {
if(dp[i][j] != -1) return dp[i][j];
if(!i) return dp[i][j] = 1;
else {
LL ans = 0;
Go(digit , 0 , 9) if(digit != 4 && !(j == 6 && digit == 2)) ans += f(i-1 , digit);
return dp[i][j] = ans;
}
}

LL calc(LL x) {
int m = 0;
while(x) {
d[m++] = x%10; x/=10;
}
LL ans = 0;
Go(i , 1 , m-1) {
Go(j , 1 , 9) if(j != 4) ans += f(i-1 , j);
}
// std::cerr <<"%% " << ans << std::endl;
int last = 0;
God(i , m-1 , 0) {
Go(j , (i == m-1) ? 1 : 0 , d[i]-1) if(j != 4 && !(last == 6 && j == 2)) ans += f(i , j);
if(d[i] == 4) break;
if(last == 6 && d[i] == 2) break;
last = d[i];
}
return ans;
}
int main() {
memset(dp , -1 , sizeof(dp));
LL l , r;
while(1) {
sc(l , r);
if(!l && !r) return 0;
//std::cout << calc(l) << std::endl;
std::cout << calc(r+1) - calc(l) << std::endl;
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×