항 저 우 전기 hdu 2089 싫어 62 [디지털 dp] [입문]

싫다
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 29117    Accepted Submission(s): 10217
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
새 학기 맞이 - 슈퍼 이지 버 전 평가 전
 
이 문 제 는 예전 에 했 던 것 입 니 다. 그 때 는 폭력 으로 넘 어 갈 수 있 었 고 dp 를 사용 할 생각 도 없 었 습 니 다. 젊 고, 그리고 오늘 돌아 와 서 지식 을 보충 할 수 있 었 습 니 다. 여러분 의 이 해 를 공유 해 드 리 겠 습 니 다 ~
우 리 는 먼저 dp [] [] 배열 에 대해 의미 와 예비 처 리 를 해 야 한다. 여기 서 dp [i] [j] 는 j 로 시작 하 는 i 자리수의 조건 에 부합 되 는 개 수 를 나타 낸다. 우리 가 여기 서 말 하 는 것 은 이해 하기 어 려 울 수 있다. 우 리 는 여기 서 밤 을 들 었 다. dp [2] [6] = 8. 60 ~ 69 에서 조건 을 만족 시 키 는 개 수, 60, 61, 63, 65, 66, 67, 68, 69 (8 개 ~) 를 나타 낸다.
우 리 는 여기 서 밤 dp [3] [0] 을 하나 더 들 었 다. 1 ~ 100 에서 조건 을 만족 시 키 는 개 수 를 나타 낸다.
그러면 dp [3] [1] 은 요?100 ~ 200 에서 조건 을 만족 시 키 는 개 수 를 나타 낸다. [100, 199]
여기 서 우 리 는 dp 배열 의 의 미 를 알 게 되 었 습 니 다. 그러면 우 리 는 예비 처 리 를 진행 합 시다. 여기 서 우 리 는 dp 배열 내 데 이 터 를 붙 이 는 김 에 참고 하 시기 바 랍 니 다.
1 1 1 1 0 1 1 1 1 9 9 9 9 0 9 8 9 9 80 80 80 80 0 80 71 80 80 711 711 711 711 0 711 631 711 711 6319 6319 6319 6319 0 6319 5608 6319 6319 56160 56160 56160 56160 0 56160 49841 56160 56160 499121 499121 499121 499121 0 499121 442961 499121 499121
dp 코드 초기 화: / / 이 부분 코드 에 대해 자세히 보고, 진지 하 게 보고, 깨 달 으 면 알 수 있 습 니 다 ~
4. 567913. 여기 서 우 리 는 전체 블록의 데 이 터 를 알 게 된 후에 (예 를 들 어 dp [2] [6] 우 리 는 무슨 뜻 인지 알 게 되 었 다. 그러나 우 리 는 전체 블록의 데 이 터 를 합 쳐 야 최종 결 과 를 얻 을 수 있다) 작은 디 테 일 을 처리 해 야 한다. 이상 의 데이터 가 있 으 면 우 리 는 현재 이 수 를 처리 하기 전에 두 가지 요소 가 필요 하 다 는 것 을 알 게 되 었 다.
1. 각 비트 의 데이터
2. 데이터 의 길이
여기 서 우 리 는 함수 로 쉽게 실현 할 수 있다.
4. 567913. 이렇게 알려 진 조건 이 있 으 면 우 리 는 데이터 에 대해 하나씩 판단 하고 처리 하면 됩 니 다 ~
우리 가 여기 서 구 하 는 [0, n) 의 만족 조건 의 개 수 는 다음 과 같다.
4. 567913. 모든 내용 이 확 정 된 후에 [n, m] 을 구 하 는 방법 도 매우 직접적 입 니 다.
[0, m] 의 개 수 를 구하 고 [0, n - 1] 의 개 수 를 구하 고 상쇄 하면 최종 득 수 를 얻 을 수 있 습 니 다. 여기 있 는 완전한 AC 코드:

    dp[0][0]=1;<span style="white-space:pre">																		</span>      //  dp   dp、  dp   dp（        dp）<span style="white-space:pre">	</span>
    for(int i=1;i<=7;i++)
    {
        for(int j=0;j<10;j++)//   i      、
        {
            for(int k=0;k<10;k++)//   i-1     、
            {
                if(!(j==6&&k==2)&&j!=4)//    
                dp[i][j]+=dp[i-1][k];
            }
        }
    }