Jimmy writes down the decimal representations of all naturalnumbers between and including m and n, (m ≤ n). How many zeroeswill he write down?Input
Input starts with an integer T (≤ 11000),denoting the number of test cases.Each case contains two unsigned 32-bit integers m andn, (m ≤ n).Output
For each case, print the case number and the number of zeroeswritten down by Jimmy.Sample Input
Output for Sample Input
510 11100 2000 5001234567890 23456789010 4294967295Case 1: 1Case 2: 22Case 3: 92Case 4: 987654304Case 5: 3825876150题意：给出区间[m,n]，求区间内的所有数共有多少个0。
思路：设dp[i][j]表示处理到第i位时，它前面共有j个0（除了前导零）。
代码：
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
ll dp[50][50];
int digit[51];int cal(ll val) {int len=0;if(val<0)return 0;if(val==0)return 1;while(val) {digit[len++]=val%10;val/=10;}memset(dp,-1,sizeof(dp));return len-1;
}// 数位位置 状态 限制 前导0标志(false==是前导0)
ll dfs(int pos,int sta,int lim,bool J) {if(pos<0)return (!J)?1:sta;if((!lim) && (J) && (dp[pos][sta]^-1)) {//无限制且非前导0return dp[pos][sta];}int len=lim?digit[pos]:9;ll ans=0;for(int i=0; i<=len; ++i) {ans+=dfs(pos-1,sta+((J)&&(i==0)),lim&&(i==len),J||i);}if(lim==0&&(J))dp[pos][sta]=ans;//必须是非前导0return ans;
}ll work(ll val) {if(val<0)return 0;if(val==0)return 1;return dfs(cal(val),0,1,0);
}ll n,m;int main() {int T;int coun=1;scanf("%d",&T);while(T--) {scanf("%lld%lld",&n,&m);printf("Case %d: %lld\n",coun++,work(m)-work(n-1));}return 0;
}