HDU 2089 不要62(数位dp)

#include <bits/stdc++.h>
using namespace std;
int a[10];
int dp[10][10];

int dfs(int pos, int pre, bool limit){
  if(pos == -1) return 1;
  if(!limit && dp[pos][pre] != -1) return dp[pos][pre];
  int up = limit ? a[pos] : 9;
  int ans = 0;
  for(int i=0;i<=up;i++){
    if(pre == 6 && i == 2) continue;
    if(i == 4) continue;
    ans += dfs(pos - 1, i, limit && i == a[pos]);
  }
  return limit ? ans : dp[pos][pre] = ans;
}

int solve(int x){
  int pos = 0;
  while(x){
    a[pos++] = x % 10;
    x /= 10;
  }
  return dfs(pos - 1, 0, true);
}

int main()
{
  int l, r;
  while(~scanf("%d%d",&l, &r)){
    if(l == 0 && r == 0) break;
    memset(dp,-1,sizeof(dp));
    printf("%d\n", solve(r) - solve(l - 1));
  }
  return 0;
}