HDU 2089:不要62（数位DP）

#include <cstdio>
#include <cstring>

int dp[15][10];
int num[120];

int dfs(int i, int now, bool iscount) 
{
    if (!iscount && dp[i][now] != -1) return dp[i][now];
    if (i == 1) {
        if (now == 4) return dp[i][now] = 0;
        else return dp[i][now] = 1;
    }
    int end = iscount?num[i-1]:9;
    int ans = 0;
    for (int d = 0; d <= end; d++) {
        if ((now == 6 && d == 2) || d == 4) continue;
        ans += dfs(i-1, d, iscount && d == end);
    }
    if (!iscount) dp[i][now] = ans;
    return ans;
}

int cal(int x) {
    int len = 0;
    while (x) {
        num[++len] = x%10;
        x /= 10;
    }
    return dfs(len+1, 0, 1);
}

int main(){ 
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n == 0 && m == 0) return 0;
        memset(dp, -1, sizeof(dp));
        printf("%d\n", cal(m)-cal(n-1));
    }
    return 0;
}