Description

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

Input

包含两个整数，A B。

Output

一个整数。

Sample Input

【输入样例一】
1 10

【输入样例二】
25 50

Sample Output

【输出样例一】
9

【输出样例二】
20

【数据规模和约定】
20%的数据，满足 1 <= A <= B <= 1000000 。
100%的数据，满足 1 <= A <= B <= 2000000000 。

求在n和m之间相邻的差要大于等于2的个数

dp[i][j]代表i位，且以j开头的数的个数。其中符合相邻的差要大于等于2 ；

计算n到m之间的个数 = 用1到m的个数 - 1到n的个数。

从高位开始，累加计数。当高位中已经不满足条件后直接退出。

忽略前导0，所以累加是前导为0的另外累加。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std ; #define LL long long LL dp[12][10] ; LL digit[12] , cnt ; void init() { memset(dp,0,sizeof(dp)) ; int i , j , k ; for(i = 0 ; i <= 9 ; i++) dp[1][i] = 1 ; for(i = 2 ; i <= 10 ;i++) for(j = 0 ; j < 10 ; j++) for(k = 0 ; k < 10 ; k++) if( abs(j-k) >= 2 ) { dp[i][j] += dp[i-1][k] ; } } LL solve(LL temp) { LL ans = 0 , i , j ; cnt = 0 ; memset(digit,0,sizeof(digit)) ; while(temp) { digit[++cnt] = temp % 10 ; temp /= 10 ; } for(j = 1 ; j < digit[cnt] ; j++) ans += dp[cnt][j] ; for(i = cnt-1 ; i > 0 ; i--) for(j = 1 ; j < 10 ; j++) ans += dp[i][j] ; for(i = cnt-1 ; i > 0 ; i--) { for(j = 0 ; j < digit[i] ; j++) if( abs(digit[i+1]-j ) >= 2 ) ans += dp[i][j] ; if( abs(digit[i+1]-digit[i]) < 2 ) break ; } return ans ; } int main() { init() ; LL a , b ; while( scanf("%lld %lld", &a, &b) != EOF ) { printf("%lld\n", solve(b+1)-solve(a) ); } return 0; }