求（一~n）中有多少个数字包含49数字

求（1~n）中有多少个数字包含49数字

#include <bits/stdc++.h>

using namespace std;

int digit[20];
long long dp[20][3];

long long DFS(int pos, int have, int flag)//have 0 表示无 1 表示前一位为4 2 表示已经有49
{
    if(pos == -1) return have == 2;
    if(!flag && dp[pos][have] != -1)
        return dp[pos][have];
    int end = flag ? digit[pos] : 9;
    long long ans = 0;
    //int nhave = have;
    for(int i=0; i<=end; i++)
        {
//            int nhave = have;
//        if(have == 1 && i != 4)
//            nhave = 0;
//        if(have == 0 && i == 4)
//            nhave = 1;
//        if(have == 1 && i == 9)
//            nhave = 2;
        int nhave = have;
        //if(i == 4) nhave = 1;
        if(have == 1)
        {
            if(i == 9) nhave = 2;
            else nhave = 0;
        }
        if(i == 4) nhave = 1;
            ans += DFS(pos-1, nhave, i == end && flag);
        }
    if(!flag)
        dp[pos][have] = ans;
    return ans;
}

long long Cal(int n)
{
    int pos = 0;
    while(n)
    {
        digit[pos++] = n % 10;
        n /= 10;
    }
    return  DFS(pos - 1, 0, 1);
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int n, T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(dp, -1, sizeof(dp));
        cout<<Cal(n)<<endl;
    }
    return 0;
}