HDU 3555 Bomb

Here's a number n, I want you to ask 0-n How many numbers in contain 49, use n- Not included 49 The number of is the answer .

#include<bits\stdc++.h>
using namespace std;

typedef long long ll;
ll dp[20][10];// Recorded in the i position , The first one is j The number of qualified 
int a[20];//
ll dfs(ll pos,ll pre,ll lim)// The current position , The first digit , Whether the previous digit is the maximum number of the previous digit 
{
    if(pos==-1) return 1;// At this point, all locations have been enumerated , Meet the requirements ;
    if(!lim&&dp[pos][pre]!=-1)
        return dp[pos][pre];
    int up=lim?a[pos]:9;//up Represents the maximum number that can be enumerated 
    ll ans=0;
    for(int i=0;i<=up;i++)
    {
        if(pre==4&&i==9)
            continue;
        ans+=dfs(pos-1,i,lim&&i==up);// If the current position has not reached the maximum number , Then there is no limit on the number of the next digit .
    }
    if(!lim) dp[pos][pre]=ans;// Save the number of qualified current states 
    return ans;
}
ll solve(ll n)
{
    int i=0;
    while(n)
    {
        a[i++]=n%10;
        n/=10;
    }
    return dfs(i-1,0,1);
}
int main()
{
    int t;
    scanf("%d",&t);
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
        ll n;
        scanf("%I64d",&n);
        printf("%I64d\n",n-solve(n)+1);
    }
    return 0;
}