数位DP

小灰灰 2022-06-15 00:40 306阅读 0赞

#### Problem Description ####

据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047 是他的幸运数字，而 74, 1234, 407 就不是他的幸运数字。

而对 C~K 来说，只要不是 QAQ 的幸运数字的数都是他的幸运数字。那么他想问你，在闭区间 \[l, r\] 中，有多少个自己的幸运数字？

#### Input ####

输入数据有多组。第 1 行输入 1 个整数 T (1 <= T <= 10000) 表示数据组数。

对于每组数据，输入 1 行，包含 2 个整数 l, r (1 <= l <= r < 10^9)，表示 C~K 要询问的区间。

#### Output ####

对于每组数据，在 1 行中输出 1 个整数，表示区间内 C~K 的幸运数字的个数。

#### Example Input ####

3
    1 1
    10 50
    1 500

#### Example Output ####

1
    40
    485
    
    #include<stdio.h>
    #include<string.h>
    int digit[12];
    int dp[12][12];
    
    int dfs(int pos,int pre,int limit) 
    {
        int i;
        int end;
        int ret=0;
        if(pos<0)
        {
            return 1;
        }
        if(!limit && dp[pos][pre]!=-1)  //说明之前递归的时候进行过这一步
        {
            return dp[pos][pre];
        }
        end=limit?digit[pos]:9;
        for(i=0;i<=end;i++)
        {
            if(!(pre==4 && i==7))   //如果上一位不是4或者当前位不是7则不满足47的条件
            {                           //然后pos-1，开始检查下一位和当前位是不是构成47的条件
                ret+=dfs(pos-1,i,limit && i==end);
            }
        }
        if(!limit)
            dp[pos][pre]=ret;
        return ret;
    }
    int calcu(int n)
    {
        int i;
        i=0;
        while(n)
        {
            digit[i++]=n%10;   //对n进行数位拆分，从低位到高位存放在digit数组中
            n/=10;
        }
        return dfs(i-1,0,1);   //i-1是最高位存放的下标，0 是前一位的数  1表示前一位已经到达了上界，如果是0
                                //代表没有到达上界
    }
    int main()
    {
        int t;
        int l,r;
        int count;
        scanf("%d",&t);
        memset(dp,-1,sizeof(dp));
        while(t--)
        {
            scanf("%d%d",&l,&r);
            count=calcu(r)-calcu(l-1);
            printf("%d\n",count);
        }
        return 0;
    }