BZOJ1026 [SCOI2009] windy数

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1026

Description

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

Input

包含两个整数，A B。

Output

一个整数。

数位DP初探，明明是水题还调了很久

dp[i][j]表示长度为i，最高位为j的windy数的数量

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 #define rep(i,l,r) for(int i=l; i<=r; i++)
 7 #define clr(x,y) memset(x,y,sizeof(x))
 8 using namespace std;
 9 int A,B,dp[12][10],t[12];
10 inline void init(){
11     clr(dp,0);
12     rep(i,0,9) dp[1][i] = 1;
13     rep(i,2,10) rep(j,0,9) rep(k,0,9)
14     if (abs(j-k) >= 2) dp[i][j] += dp[i-1][k];
15 }
16 int calc(int x){
17     int h = 0, ans = 0;
18     while (x){
19         t[++h] = x % 10; x /= 10;
20     }
21     rep(i,1,h-1) rep(j,1,9) ans += dp[i][j];
22     rep(j,1,t[h]-1) ans += dp[h][j];
23     for(int i=h; i>=2; i--){
24         rep(j,0,t[i-1]-1)
25         if (abs(t[i] - j) >= 2) ans += dp[i-1][j];
26         if (abs(t[i] - t[i-1]) < 2) break;
27     }
28     return ans;
29 }
30 int main(){
31     scanf("%d%d",&A,&B);
32     init();
33     printf("%d
",calc(B+1)-calc(A));
34     return 0;
35 }

View Code