[HDU] 4734 F(x) 디지털 DP

전송문:【HDU】4734F(x)
제목 분석: F(x)가 4599에 불과한 것을 발견하여 dp[10][5000]를 열었고 dp[i][j]는 i위까지 j의 크기로 모을 수 있는 개수를 나타냈다.그리고 디지털 DP를 만들 수 있습니다. dp수 그룹을 처음에 초기화하면 됩니다.
주의: 두 번째는 반드시 남은 크기를 표시해야 합니다. 이렇게 하면 매번 dp가 다시 계산해야 하기 때문에 시간을 초과하지 않습니다. (? 아마도 더 좋은 방법도 있을 것입니다.)
코드는 다음과 같습니다.

#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#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 clr( a , x ) memset ( a , x , sizeof a )

int dp[10][5000] ;
int digit[10] ;
int A , B ;

int dfs ( int cur , int limit , int sum ) {
	if ( sum < 0 ) return 0 ;
	if ( cur == -1 ) return 1 ;
	if ( !limit && ~dp[cur][sum] ) return dp[cur][sum] ;
	int ans = 0 , n = limit ? digit[cur] : 9 ;
	For ( i , 0 , n ) ans += dfs ( cur - 1 , limit && i == n , sum - i * ( 1 << cur ) ) ;
	return limit ? ans : dp[cur][sum] = ans ;
}

void solve () {
	int n1 = 0 , sum = 0 ;
	scanf ( "%d%d" , &A , &B ) ;
	rep ( i , 0 , 9 ) {
		sum += A % 10 * ( 1 << i ) ;
		A /= 10 ;
	}
	while ( B ) {
		digit[n1 ++] = B % 10 ;
		B /= 10 ;
	}
	int ans = dfs ( n1 - 1 , 1 , sum ) ;
	printf ( "%d
" , ans ) ;
}

int main () {
	int T , cas = 0 ;
	scanf ( "%d" , &T ) ;
	clr ( dp , -1 ) ;
	while ( T -- ) {
		printf ( "Case #%d: " , ++ cas ) ;
		solve () ;
	}
	return 0 ;
}