[uestc oj] H. - 구 선생님 은 여동생.

H. - 구 선생님 은 여동생.
Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit 
Status
구 선생님 이 잘 생 겼 다 는 것 은 누구나 다 알 고 있 기 때문에 그의 여동생 을 쫓 아 다 니 는 것 이 많 을 것 이다.
그러나 너 는 구 선생님 이 매우 전일 한 사람 이라는 것 을 알 고 있 기 때문에 그의 마음 속 에는 한 사람 만 있 을 수 있다.
그래서 그 는 그 를 쫓 아 다 니 는 많은 여동생 중에서 하 나 를 고 르 기로 결정 했다.그래서 장 신 은 구 선생님 께 아 이 디 어 를 내 주 었 다. 이미 몇 명의 여동생 이 있 는데 마침 그들 에 게 l 에서 r 까지 번 호 를 줄 수 있어 서 모든 여동생 에 게 단독 숫자 가 있 고 마침 r - l + 1 명의 여동생 이 있다.
장 신 은 우리 가 운 이 나 쁜 여자 아 이 를 가 져 서 는 안 된다 고 말 했다. 장 신 은 또 두 개의 숫자 62 와 4 를 주 었 다. 만약 에 여동생 의 번호 안에 62 (연속 적 이 어야 한다) 나 4 가 있다 면 그 가 지금 너 에 게 l 과 r 를 주 고 몇 명의 여동생 이 1 차 에 남 을 수 있 는 지 물 었 다.
Input
입력 한 것 은 모두 정수 대 l, r (0 < l ≤ r < 1000000) 이 며, 모두 0 의 정수 대 를 만나면 입력 이 끝 납 니 다.
Output
 각 그룹의 데이터 출력 은 한 줄 을 차지 하고, l 과 r 출력 에 대해 몇 명의 여동생 이 1 라운드 에서 배제 되 지 않 을 수 있 습 니까?
디지털 dp 는 현재 비트 결정 에 영향 을 줄 수 있 는 것 은 앞의 비트 가 6 인지 아 닌 지 를 sta 로 기록 한 다음 에 현재 비트 의 선택 은 뒤의 디지털 선택의 상계 에 영향 을 줄 수 있 기 때문에 flag 를 만 듭 니 다.

#include <stdio.h>



int dp[8][2];//j     6    dp[i][j]     i,     j  10^(i+1)          

int vis[8][2];

int dig[8];



int dfs(int len,int sta,bool flag)

{

  if(len==0)return 1;

  if(!flag&&vis[len][sta])return dp[len][sta];

  int ans=0,up=flag?dig[len]:9;

  for(int i=0;i<=up;i++)

  {

    if(i==4||(sta&&i==2) )//    4     6    2     

      continue;

    ans+=dfs(len-1,i==6?1:0,flag&&i==up);

  }

  if(!flag)

    vis[len][sta]=1,dp[len][sta]=ans;

  return ans;

}



int Get(int n)

{

  int len = 0;

  while(n)

  {

    dig[++len]=n%10;

    n/=10;

  }

  return dfs(len,0,true);

}



int main()

{

    int l,r;

    while(scanf("%d%d",&l,&r)==2)

    {

      if(l==0&&r==0)break;

        printf("%d
",Get(r)-Get(l-1));

    }

    return 0;

}