本文主要是介绍【HDU】3652 B-number 数位DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】3652 B-number
题目分析：记录数字对13取模后的状态。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;typedef long long LL ;#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 travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )const int MAXN = 65 ;int dp[MAXN][10][2][2][13] ;
int ten[MAXN] ;
int vis[MAXN][10][2][2][13] , Time ;
int num[MAXN] ;
int n ;int dfs ( int cur , int j , int flag , int has , int number ) {//if ( cur == -1 ) printf ( "%d\n" , number ) ;if ( cur == -1 ) return has && number % 13 == 0 ;int& tmp = dp[cur][j][flag][has][number * ten[cur] % 13] ;if ( vis[cur][j][flag][has][number * ten[cur] % 13] == Time ) return tmp ;vis[cur][j][flag][has][number * ten[cur] % 13] = Time ;tmp = 0 ;if ( flag ) {rep ( i , 0 , 10 ) {if ( j == 1 && i == 3 ) tmp += dfs ( cur - 1 , i , 1 , 1 , number * 10 + i ) ;else tmp += dfs ( cur - 1 , i , 1 , has , number * 10 + i ) ;}} else {rep ( i , 0 , num[cur] ) {if ( j == 1 && i == 3 ) tmp += dfs ( cur - 1 , i , 1 , 1 , number * 10 + i ) ;else tmp += dfs ( cur - 1 , i , 1 , has , number * 10 + i ) ;}if ( j == 1 && num[cur] == 3 ) tmp += dfs ( cur - 1 , num[cur] , 0 , 1 , number * 10 + num[cur] ) ;else tmp += dfs ( cur - 1 , num[cur] , 0 , has , number * 10 + num[cur] ) ;}return tmp ;
}void solve () {int n1 = 0 ;while ( n ) {num[n1 ++] = n % 10 ;n /= 10 ;}++ Time ;clr ( dp , 0 ) ;int count = dfs ( n1 - 1 , 0 , 0 , 0 , 0 ) ;printf ( "%d\n" , count ) ;
}int main () {clr ( vis , 0 ) ;Time = 0 ;ten[0] = 1 ;rep ( i , 1 , MAXN ) ten[i] = ten[i - 1] * 10 ;while ( ~scanf ( "%d" , &n ) ) solve () ;return 0 ;
}这篇关于【HDU】3652 B-number 数位DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
