BZOJ-1026: [SCOI2009]windy数（数位统计

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

裸的数位统计，不过还是很恶心额。。不使劲对拍的话死活A不了555

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define rep( i , x ) for ( ll i = 0 ; i < x ; ++ i )
#define maxn 20
 
typedef long long ll ;
 
ll f[ maxn ][ 10 ] , pre[ maxn ][ 10 ] , cnt , ans ;
 
ll N[ maxn ] , a , b ; 
 
void dfs( ll now ) {
    if ( ! now ) {
        rep( i , N[ now ] + 1 ) pre[ now ][ i ] = 1 ;
        return ; 
    }
    rep( i , N[ now ] ) {
        rep( j , 10 ) if ( abs( i - j ) >= 2 ) {
            pre[ now ][ i ] += f[ now - 1 ][ j ] ;
        }
    }
    dfs( now - 1 ) ;
    rep( i , 10 ) if ( abs( N[ now ] - i ) >= 2 ) {
        pre[ now ][ N[ now ] ] += pre[ now - 1 ][ i ] ;
    }
}
 
void cal( ll x ) {
    if ( ! x ) {
        cnt = 0 ; 
        return ;
    }
    ll len = 0 ; 
    for ( ; x ; x /= 10 ) N[ len ++ ] = x % 10 ;
    if ( len == 1 ) {
        cnt = N[ 0 ] + 1 ; return ; 
    }
    memset( f , 0 , sizeof( f ) ) ;
    rep( i , len ) {
        if ( ! i ) {
            rep( j , 10 ) f[ i ][ j ] = 1 ; 
        } else {
            rep( j , 10 ) rep( k , 10 ) if ( abs( j - k ) >= 2 ) {
                f[ i ][ j ] += f[ i - 1 ][ k ] ;
            }
        }
    }
    memset( pre , 0 , sizeof( pre ) ) ;
    dfs( len - 1 ) ;
    cnt = 0 ;
    rep( i , 10 ) if ( i ) cnt += pre[ len - 1 ][ i ] ;
    rep( i , len - 1 ) rep( j , 9 ) cnt += f[ i ][ j + 1 ] ;
}
 
int main(  ) {
    scanf( "%lld%lld" , &a , &b ) ;
    cal( b ) ;
    ans = cnt ;
    cal( a - 1 ) ;
    printf( "%lld\n" , ans - cnt ) ;
    return 0 ;
}