bzoj1026

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;
}