数位dp（D

题目链接：https://cn.vjudge.net/contest/278036#problem/D

题目大意：T组测试数据，每一次输入两个数，求的是在这个区间里面，有多少个0，比如说19203包括一个0,123包括0个0。

具体思路：数位dp，对于当前的这一位的所有情况，先看一下这一位上之前的数是不是都是0，如果都是0的话，那么这一位上即使是0也不能计算在内，因为00还是1个0。dp[i][j]代表的是第i位之前有多少0,注意，对于初始条件，我们设置为这个数的前面也都是0，举个例子1234，我们在枚举第一位的所有情况的时候，如果是0的话，是不应该记录在内的，所以我们设置初始位置也存在前导0.

AC代码：

 1 #include<iostream>
 2 #include<stack>
 3 #include<iomanip>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<stdio.h>
 7 #include<algorithm>
 8 #include<string>
 9 using namespace std;
10 # define ll long long
11 const int maxn =10+10;
12 ll dig[maxn],dp[maxn][maxn];
13 ll dfs(int len,int t,bool head0,bool fp)
14 {
15     if(!len)
16     {
17         if(head0)//一开始在这个地方卡住了，我们需要记录的是第i位之前存在多少0，那么0的时候就是一个，1-9也是1个。
18             return 1;
19         return t;
20     }
21     if(!fp&&!head0&&dp[len][t]!=-1)
22         return dp[len][t];
23     ll ans=0,fmax = fp?dig[len]:9;
24     for(int i=0; i<=fmax; i++)
25     {
26         if(head0)
27             ans+=dfs(len-1,0,head0&&i==0,fp&&i==fmax);//按照递归的形式，只有当前面的都是0的时候，当前这一位也是0的时候，才算是前导0
28         else
29             ans+=dfs(len-1,t+(i==0),head0&&i==0,fp&&i==fmax);
30     }
31     if(!fp&&!head0)
32         dp[len][t]=ans;
33     return ans;
34 }
35 ll cal(ll t)
36 {
37     int num=0;
38     memset(dp,-1,sizeof(dp));
39     while(t)
40     {
41         dig[++num]=t%10;
42         t/=10;
43     }
44     return dfs(num,0,1,1);
45 }
46 int main()
47 {
48     int T;
49     scanf("%d",&T);
50     int Case=0;
51     while(T--)
52     {
53         ll n,m;
54         scanf("%lld %lld",&n,&m);
55         printf("Case %d: ",++Case);
56         printf("%lld
",cal(m)-cal(n-1));
57     }
58     return 0;
59 }
60