HDU2089 不要62 标准数位DP

[数位DP](https://www.luogu.org/blog/mak2333/shuwei) 一道标准的数位DP模板题，很容易想到dfs多传一下上一位 ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long ll dp[15][15]; ll num[15],n,m; ll dfs(ll pos,ll last,bool limit) { if(pos==0)return 1; if(!limit&&dp[pos+1][last]!=-1) return dp[pos+1][last]; ll up=limit?num[pos]:9; ll ans=0; for(ll i=0;i<=up;i++) { if(i!=4&&!(last==6&&i==2)) ans+=dfs(pos-1,i,limit&&(i==up)); } if(!limit) dp[pos+1][last]=ans; return ans; } ll solve(ll x) { ll len=0; memset(num,0,sizeof(num)); while(x) { num[++len]=x%10; x=x/10; } return dfs(len,0,1); } int main() { memset(dp,-1,sizeof(dp)); while(scanf("%lld %lld",&n,&m)) { if(n==0&&m==0) return 0; printf("%lld\n",solve(m)-solve(n-1)); } } ```