(디지털 DP 1.1) hdu 2089 62 (구간 [a, b] 에 4, 64 가 포함 되 지 않 은 수의 개 수 를 구하 십시오)

제목:
싫다
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 23759    Accepted Submission(s): 8128
Problem Description
항 저 우 사람들 은 그 멍청 하고 끈적끈적 한 사람들 을 62 라 고 부른다.
항 저 우 교통 관리 국 은 택시 번호판 을 늘 리 는 경우 가 많다. 최근 에 좋 은 소식 이 나 왔 다. 앞으로 번호판 을 올 리 면 더 이상 불길 한 숫자 가 포함 되 지 않 는 다. 그러면 개별 택시 기사 와 승객 들 의 심리 적 장 애 를 없 애고 대중 에 게 더욱 안전하게 서 비 스 를 제공 할 수 있다.
불길 한 숫자 는 4 나 62 가 들 어 있 는 모든 번호 다.예 를 들 면:
62315 73418 88914
모두 불길 한 번호 에 속한다.그러나 61152 에는 6 과 2 가 들 어 있 지만 62 일련 번 호 는 아니 기 때문에 불길 한 숫자 에 속 하지 않 는 다.
당신 의 임 무 는 매번 제시 하 는 번호판 구간 번호 에 대해 서 는 교통 관리 국 이 이번 에는 실제로 몇 대의 새 택시 에 번호판 을 찍 어야 하 는 지 추정 하 는 것 입 니 다.
 
Input
입력 한 것 은 모두 정수 대 n, m (0 < n ≤ m < 1000000) 이 며, 모두 0 의 정수 대 를 만나면 입력 이 끝 납 니 다.
 
Output
모든 정수 쌍 에 대해 불길 한 숫자 가 없 는 통계 개 수 를 출력 하 는데 이 수 치 는 한 줄 의 위 치 를 차지한다.
 
Sample Input

   
   
   
   

    
    
    
    1 100
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    80
   
   
   
   

 
Author
qianneng
 
Source
새 학기 맞이 - 슈퍼 이지 버 전 평가 전
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   2090  2091  2092  2086  2085 
제목 분석:
              디지털 DP.
다음은 디지털 DP 에 대한 간단 한 소개 입 니 다.
1. 디지털 DP 는 보통 '한 구간 에서 상황 에 맞 는 수 를 구 하 는 개수' 와 같은 상황 을 해결 하 는 데 사용 된다.이 때 는 종종 옮 겨 다 닐 수 없다. 그렇지 않 으 면 시간 을 초과 할 것 이다.
코드 는 다음 과 같 습 니 다:

/*
 * hdu2089.cpp
 *
 *  Created on: 2015 4 13 
 *      Author: Administrator
 */


#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 10;//   <10 WA

int dp[maxn][maxn];//dp[i][j]   j   i            


/**
 *    ,   dp[i][j]
 */
void init(){
	int i;
	int j;
	int k;
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(i = 1 ; i <= 7 ; ++i){//      .            1~1000000。     7     
		for(j = 0 ; j < 10 ; ++j){//   i       
			for(k = 0 ; k < 10 ; ++k){//   (i-1)       
				//       4 &&   62    
				if(j != 4 && !(j == 6 && k == 2)){
					dp[i][j] += dp[i-1][k];//       k   i-1       
				}
			}
		}
	}
}

/**
 *   [1,n)         
 */
int solve(int n){
	init();//   

	/**
	 *   58     .
	 * digit[1] = 8;
	 * digit[2] = 5;
	 *    1  
	 */
	int digit[maxn];

	int len = 0;
	while(n > 0){// n         digit 
		digit[++len] = n%10;
		n /= 10;
	}
	digit[len+1] = 0;//     0

	int ans = 0;//         
	int i;
	int j;
	for(i = len ; i > 0 ; --i){//               
		for(j = 0 ; j < digit[i] ; ++j){//          
			//       4 &&   62    
			if(j != 4 && !(j == 2 && digit[i+1] == 6)){
				ans += dp[i][j];//    j   i                    
			}
		}

		//                
		if(digit[i] == 4 || (digit[i] == 2 && digit[i+1] == 6)){
			break;//    .            
		}
	}

	return ans;
}


int main(){
	int l,r;
	while(scanf("%d%d",&l,&r)!=EOF,l||r){
		printf("%d
",solve(r+1) - solve(l));
	}

	return 0;
}