HDU 2089 不要62 (数位DP)

简单的数位DP。

代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
const int mod=100000000;
const int INF=0x3f3f3f3f;
const double eqs=1e-8;
int dp[11][11], c[11];
int dfs(int cnt, int pre, int maxd, int zero)
{
    if(cnt==-1) return 1;
    if(maxd&&zero&&dp[cnt][pre]!=-1) return dp[cnt][pre];
    int i, r, ans=0;
    r=maxd?9:c[cnt];
    for(i=0;i<=r;i++){
        if(i==4) continue ;
        if(!zero||!(i==2&&pre==6)){
            ans+=dfs(cnt-1,i,maxd||i<r,zero||i);
        }
    }
    if(maxd&&zero) dp[cnt][pre]=ans;
    return ans;
}
int Cal(int x)
{
    int i, cnt=0;
    while(x){
        c[cnt++]=x%10;
        x/=10;
    }
    return dfs(cnt-1,-1,0,0);
}
int main()
{
    int n, m;
    memset(dp,-1,sizeof(dp));
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m){
        printf("%d\n",Cal(m)-Cal(n-1));
    }
    return 0;
}