bzoj1026: [SCOI2009]windy数（数位DP）

bzoj1026

题目描述：求A到B之间不含前导0且相邻两位数字的差至少为2的数的个数。

输入格式：两个整数，表示A和B。

输出格式：一个整数，表示答案。

输入样例：

1 10

输出样例：

解析：数位DP的入门题，dp[pos][pre]表示搜到第pos位，上一位是pre的数的个数。注意一下前导0就没多大问题。

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 using namespace std;
 5 
 6 int a, b, dp[15][10], bit[15], cnt;
 7 
 8 int dfs(int pos, int lead, int limit, int pre) {
 9     if (!pos) return dp[pos][pre] = 1;
10     if (limit && lead && ~dp[pos][pre]) return dp[pos][pre];
11     int len = limit ? 9 : bit[pos], ans = 0;
12     for (int i = 0; i <= len; ++ i) {
13       if (abs((double)i - pre) < 2) continue; //别问我为什么abs要强转成double，不这么打在bzoj上会ce QAQ 
14       int tmp = i;
15       if (i == 0 && !lead) tmp = -3; //对前导0特殊处理 
16       ans += dfs(pos - 1, lead || i > 0, limit || i < len, tmp);
17     }
18     if (lead && limit) dp[pos][pre] = ans;
19     return ans;
20 }
21 
22 int solve(int x) {
23     cnt = 0;
24     while (x) {
25       bit[++ cnt] = x % 10;
26       x /= 10;
27     }
28     memset(dp, -1, sizeof(dp));
29     return dfs(cnt, 0, 0, -3);
30 }
31 
32 int main() {
33     scanf("%d %d", &a, &b);
34     printf("%d", solve(b) - solve(a - 1));
35     return 0;
36 }