找0~n 有多少个含有49的数直接DP

dp[i][j][k]  到第 i位  前面一位是j  k是是否含有49了  随便记录一下就可以了

 

#include 
      
       #include
       
        #include
        
         using namespace std ;#define ll long longint dig[20];ll dp[20][10][2];ll dfs(int len,int now,int ok,int e){    if(len<0)        return (ok==1);    if(!e&&dp[len][now][ok]!=-1)        return dp[len][now][ok];    int u=e?dig[len]:9;    ll ans=0;    for(int i=0;i<=u;i++)    {        if(now==4&&i==9)            ans=ans+dfs(len-1,i,1,e&&(i==u));        else            ans=ans+dfs(len-1,i,ok,e&&(i==u));    }    if(!e)        dp[len][now][ok]=ans;    return ans;}ll calc(ll n){    int cnt=0;    while(n)    {        dig[cnt++]=n%10;        n=n/10;    }    return dfs(cnt-1,0,0,1);}int main(){    memset(dp,-1,sizeof(dp));    int t;    scanf("%d",&t);    while(t--)    {        ll n;        scanf("%lld",&n);        printf("%lld\n",calc(n));    }    return 0;}