【BZOJ】1026: [SCOI2009]windy数 数位DP

本文主要是介绍【BZOJ】1026: [SCOI2009]windy数 数位DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【BZOJ】1026: [SCOI2009]windy数

题目分析：数位DP水题。

代码如下：

#include <stdio.h>
#include <cstring>
#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 11 ;int num[MAXN] ;
int dp[MAXN][MAXN][2][2] ;
int vis[MAXN][MAXN][2][2] ;
int a , b , n ;int dfs ( int cur , int j , int flag , int num[] , int pre_zero ) {if ( cur == 0 ) return 1 ;if ( vis[cur][j][flag][pre_zero] ) return dp[cur][j][flag][pre_zero] ;vis[cur][j][flag][pre_zero] = 1 ;dp[cur][j][flag][pre_zero] = 0 ;if ( flag ) {rep ( i , 0 , 10 ) {if ( pre_zero ) {dp[cur][j][flag][pre_zero] += dfs ( cur - 1 , i , 1 , num , !i ) ;} else if ( abs ( j - i ) >= 2 ) {dp[cur][j][flag][pre_zero] += dfs ( cur - 1 , i , 1 , num , 0 ) ;}}} else {rep ( i , 0 , num[cur] ) {if ( pre_zero ) {dp[cur][j][flag][pre_zero] += dfs ( cur - 1 , i , 1 , num , !i ) ;} else if ( abs ( j - i ) >= 2 ) {dp[cur][j][flag][pre_zero] += dfs ( cur - 1 , i , 1 , num , 0 ) ;}}if ( pre_zero ) {dp[cur][j][flag][pre_zero] += dfs ( cur - 1 , num[cur] , 0 , num , !num[cur] ) ;} else if ( abs ( j - num[cur] ) >= 2 ) {dp[cur][j][flag][pre_zero] += dfs ( cur - 1 , num[cur] , 0 , num , 0 ) ;}}return dp[cur][j][flag][pre_zero] ;
}int solve ( int number ) {clr ( vis , 0 ) ;n = 0 ;while ( number ) {num[++ n] = number % 10 ;number /= 10 ;}int ans = dfs ( n , 0 , 0 , num , 1 ) ;//printf ( "%d\n" , ans ) ;return ans ;
}int main () {while ( ~scanf ( "%d%d" , &a , &b ) ) printf ( "%d\n" , solve ( b ) - solve ( a - 1 ) ) ;return 0 ;
}

这篇关于【BZOJ】1026: [SCOI2009]windy数 数位DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---