LightOJ 1140 How Many Zeroes?(数位dp 记忆化搜索方法)

题意：给你m，n问[m，n]之间所有数字包含多少个0

题目链接：点击打开链接

//真苦逼  这个oj用long long 我用__int64 提交老wa
// 其实挺简单的一道题
#include<stdio.h>
#include<string.h>

long long dp[30][30][2];//dp[pos][s][first] pos 表示位置 s 表示当前位置前有多少个0 first标记是不是前面全部为0 
int digit[30];


long long dfs(int pos,int s,int first,int doing)
{
    if(pos==-1)return s;
    if(!doing && dp[pos][s][first]!=-1)return dp[pos][s][first];//记忆化
    int End,i;
    long long ans=0;
    End=doing ?digit[pos]:9;//判断当前是否是枚举上界
    for(i=0;i<=End;i++)
    {
        if(first==1&&i==0)//如果前面不全是0  当前位置是0 则s+1
            ans+=dfs(pos-1,s+1,1,doing &&i==End);
        else if(i==0)//如果全面全是0 当前也是0 则first仍标记为0
            ans+=dfs(pos-1,s,0,doing &&i==End);
        else//否则i不为0 first标记为1
            ans+=dfs(pos-1,s,1,doing &&i==End);
    }
    if(!doing)
        dp[pos][s][first]=ans;
    return ans;
}
long long solve( long long x)
{
    if(x<0)return 0;
    memset(dp,-1,sizeof(dp));
    memset(digit,0,sizeof(digit));
    int l;
    l=0;
    while(x>0)
    {
        digit[l++]=x%10;
        x=x/10;
    }
    return dfs(l-1,0,0,1)+1;
}
int main()
{
    int t,v=1;
     long long a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&a,&b);
        printf("Case %d: %lld\n",v++,solve(b)-solve(a-1));
    }
    return 0;
}