[BZOJ1799] - 디지털 DP.

앞에서 말하다

수수께끼 같은 디지털 DP...

제목.

BZOJ1799 전송문

제면

a, b를 제시하고 [a, b]에서 여러분의 숫자와 원수를 정제할 수 있는 개수를 구하세요.(이런 짧고 날카로운 문제면을 좋아한다=w=)a,b는 모두 롱롱 범위 내에 있다

해법

이 디지털 DP는 보통처럼 할 수 없습니다.평상시의 사고방식에 따라 dp[i][j][k]를 정의하여 현재 앞의 i위, 수위와 j, 숫자 모드 수위와 뒤의 k로 정의한다. R의 dp를 한 번 뛰고 L-1의 dp를 한 번 더 뛰지만 한 번 뛰면 안 된다. 앞의 모드와 뒤의 모드는 상관없기 때문에 사이를 돌릴 수 없다.그래서 이 문제는 숫자와 (즉 모수)를 매거하고 모든 숫자와 dfs를 한 번씩 뛰어야 한다. 왜냐하면 숫자는longlong 범위 내에서 숫자와 최대는 9*18=162밖에 되지 않기 때문에 통과할 수 있다.

큰 상수를 가진 코드

#include 
#include 
#include 
using namespace std ;

long long L , R , dp[20][165][165] ;
int w[20] , cnt ;

void div( long long x ){
    cnt = 1 ;
    while( x ){
        w[cnt] = x%10 ;
        x /= 10 ; cnt ++ ;
    } cnt -- ;
}

long long dfs( int dep , int sum , int am , int mmod , bool limit ){
    if( dep == 0 ) return am == 0 && sum == mmod ;
    if( sum > mmod ) return 0 ; 
    if( !limit && dp[dep][sum][am] != -1 ) return dp[dep][sum][am] ;
    int lim = ( limit ? w[dep] : 9 ) ;
    long long rt = 0 ;
    for( int i = 0 ; i <= lim ; i ++ )
        rt += dfs( dep - 1 , sum + i , ( am * 10 + i )%mmod , mmod , limit && i == lim ) ;
    if( !limit ) dp[dep][sum][am] = rt ;
    return rt ;
}

void solve(){
    long long ans = 0 ;
    div( R ) ;
    for( int i = 1 ; i <= 162 ; i ++ ){
        //printf( "now :: %d
" , i ) ;
        memset( dp , -1 , sizeof( dp ) ) ;
        ans += dfs( cnt , 0 , 0 , i , true ) ;
    }
    div( L - 1 ) ;
    for( int i = 1 ; i <= 162 ; i ++ ){
        memset( dp , -1 , sizeof( dp ) ) ;
        ans -= dfs( cnt , 0 , 0 , i , true ) ;
    }
    printf( "%lld" , ans ) ;
}

int main(){
    scanf( "%lld%lld" , &L , &R ) ;
    solve() ;
}