数位dp:


数位dp一般用于求数a~数b之间符合条件的数字个数,如30~40883之间不含47的数字个数

由前缀和【a,b】=【a,0】-【b-1,0】有:ans=solve(b)-solve(a-1);

具体用法请参考【数位dp】专题下的例题

大佬博客1https://blog.csdn.net/wust_zzwh/article/details/52100392

大佬博客2:https://www.cnblogs.com/zbtrs/p/6106783.html

各个参数:


pos:当前处理的位数,第pos位

pre:前一位上放入的数字

sta:根据题目不同有所变化,记录前一位的数字,如只需判断前一位是否是6,sta有1和0两种状态,6和其他非6的数字

limit:上限条件,limit位true当且仅当 第pos位前的几位都达到了上限

dp[pos][pre]:记忆化数组

ll dfs(ll pos,ll pre,ll sta,bool limit)
{
    if(pos==0) return 0;//计算方法不同放回值不同,1 or 0
    if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];//优化,防超时
    ll sum=0;
    ll up=limit?a[pos]:9;//第pos位的最大值 根据第pos位前的几位是否都达到了上限来判断
    for(ll i=0;i<=up;i++)
    {
        if(pre==4&&i==9)//根据具体题目变换 计算方法 和 继续dfs的条件
            sum+=limit?n%z[pos-1]+1:z[pos-1];
            else
          sum+=dfs(pos-1,i,i==4,limit && i==a[pos]);
    }
    if(!limit) dp[pos][sta]=sum;//记忆化
    return sum;
}
ll solve(ll x)
{
    ll i=0;
    while(x)
    {
        a[++i]=x%10;//存每一位数,下标从1开始存
        x/=10;
    }
    return  dfs(i,-1,0,true);
}

    z[0]=1;
    for(int i=1;i<=30;i++)
        z[i]=z[i-1]*10;//可能会用到