bzoj1026 windy数 题解 题解: 代码:

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数?

题解:

很简单的一道题,数位dp,不过我是用的记忆化搜索,感觉比递推好写。

代码:

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
#define REP(i, a, b) for(int i = a; i <= b; i ++)
#define REPG(i, x) for(int i = head[x]; i; i = g[i].nxt)
#define clr(x, y) memset(x, y, sizeof(x));
using namespace std;
typedef long long LL;
typedef double LF;
LL (LL a, LL b){return a > b ? a : b;}
LL Min(LL a, LL b){return a < b ? a : b;}
LL abs(LL x){return x > 0 ? x : -x;}
const int MAXN = 25;
int a, b, num[MAXN], f[MAXN][MAXN];
inline int read(){
int r = 0, z = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') z = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0'; ch = getchar();}
return r * z;
}
int dfs(int len, int lst, bool sx){
if(len <= 0) return 1;
if(!sx && f[len][lst] != -1 && lst >= 0) return f[len][lst];
int cnt = 0, p, maxx = (sx ? num[len] : 9);
for(int i = 0; i <= maxx; i ++){
if(abs(i - lst) < 2) continue;
p = i;
if(i == 0 && lst == -10) p = lst;
cnt += dfs(len - 1, p, sx && (i == maxx));
}
if(lst >= 0 && !sx) f[len][lst] = cnt;
return cnt;
}
int solve(int x){
int k = 0;
while(x){num[++ k] = x % 10; x/= 10;}
clr(f, -1); return dfs(k, -10, 1);
}
void work(){
a = read(), b = read();
printf("%dn", solve(b) - solve(a - 1));
}
int main(){
work();
return 0;
}