bzoj 1026[SCOI2009]windy数 - 数位dp
标签：cstring else -- init win close view gpo space
1026: [SCOI2009]windy数
Time Limit: 1 Sec Memory Limit: 162 MB
Description
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
Input
Output
Sample Input
【输入样例一】
1 10
【输入样例二】
25 50
Sample Output
【输出样例一】
9
【输出样例二】
20
HINT
【数据规模和约定】
100%的数据，满足 1
比较简单的数位dp
预处理 f[i][j] 表示到枚举到第i为首位为j的种数。
转移方程：
if(abs(j - k) >= 2 || i == 1)
f[i][j] += f[i - 1][k];
回来算的时候位数不足的要单独处理一下
1 #include 2 #include 3 #include 4 #include
5 #define LL long long
6
7 using namespace std;
8
9 int tot = 0;
10 int A, B;
11 int d[15];
12 int f[20][20];
13 inline LL read()
14 {
15 LL x = 0, w = 1; char ch = 0;
16 while(ch ‘0‘ || ch > ‘9‘) {
17 if(ch == ‘-‘) {
18 w = -1;
19 }
20 ch = getchar();
21 }
22 while(ch >= ‘0‘ && ch ‘9‘) {
23 x = x * 10 + ch - ‘0‘;
24 ch = getchar();
25 }
26 return x * w;
27 }
28
29 void init()
30 {
31 f[0][0] = 1;
32 for(int i = 1; i 10; i++) {
33 for(int j = 0; j 9; j++) {
34 for(int k = 0; k 9; k++) {
35 if(abs(j - k) >= 2 || i == 1) {
36 f[i][j] += f[i - 1][k];
37 }
38 }
39 }
40 }
41 }
42
43 LL cal(int num)
44 {
45 int ans = 0;
46 tot = 0;
47 while(num) {
48 d[++tot] = num % 10;
49 num = num / 10;
50 }
51 d[tot + 1] = 1e5;
52 for(int i = tot; i >= 1; i--) {
53 if(i == tot) {
54 for(int j = 1; j ) {
55 ans += f[i][j];
56 }
57 } else {
58 if(abs(d[i + 1] - d[i + 2]) 2) {
59 break;
60 }
61 for(int j = 0; j ) {
62 if(abs(d[i + 1] - j) >= 2) {
63 ans += f[i][j];
64 }
65 }
66 }
67 }
68 // cout
69 for(int i = tot - 1; i >= 1; i--) {
70 for(int j = 1; j 9; j++) {
71 ans += f[i][j];
72 }
73 }
74 return ans;
75 }
76 int main()
77 {
78 init();
79 A = read(), B = read();
80 // cout
81 printf("%d\n", cal(B + 1) - cal(A));
82 return 0;
83 }
View Code
bzoj 1026[SCOI2009]windy数 - 数位dp
标签：cstring else -- init win close view gpo space
原文地址：https://www.cnblogs.com/wuenze/p/8438366.html
评论