数位DP-蒲公英云

数位DP

小灰灰 2022-06-15 00:40 454阅读 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

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;
}