本文主要是介绍【HDU】3709 Balanced Number 数位DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】3709 Balanced Number
题目分析：枚举重心的位置再进行数位DP。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;typedef long long LL ;#pragma comment(linker, "/STACK:16777216")#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 )LL dp[20][10][2][2000] ;
int vis[20][10][2][2000] , Time ;
int num[20] ;
int point ;
LL x , y ;LL dfs ( int cur , int j , int flag , int number ) {if ( cur == 0 ) return !number ;if ( vis[cur][j][flag][number] == Time ) return dp[cur][j][flag][number] ;vis[cur][j][flag][number] = Time ;LL& ans = dp[cur][j][flag][number] = 0 ;if ( flag ) {rep ( i , 0 , 10 ) {int tmp = number + i * ( cur - point ) ;if ( tmp >= 0 ) ans += dfs ( cur - 1 , i , 1 , tmp ) ;}} else {rep ( i , 0 , num[cur] ) {int tmp = number + i * ( cur - point ) ;if ( tmp >= 0 ) ans += dfs ( cur - 1 , i , 1 , tmp ) ;}int tmp = number + num[cur] * ( cur - point ) ;if ( tmp >= 0 ) ans += dfs ( cur - 1 , num[cur] , 0 , tmp ) ;}return ans ;
}LL deal ( LL n ) {if ( n == -1 ) return 0 ;int n1 = 0 ;while ( n ) {num[++ n1] = n % 10 ;n /= 10 ;}LL ans = 0 ;For ( i , 1 , n1 ) {point = i ;++ Time ;ans += dfs ( n1 , 0 , 0 , 0 ) ;}return ans - n1 + 1 ;
}void solve () {scanf ( "%I64d%I64d" , &x , &y ) ;printf ( "%I64d\n" , deal ( y ) - deal ( x - 1 ) ) ;
}int main () {int T ;clr ( vis , 0 ) ;Time = 0 ;scanf ( "%d" , &T ) ;while ( T -- ) solve () ;return 0 ;
}这篇关于【HDU】3709 Balanced Number 数位DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
