[原创]LightOJ 1140 How Many Zeroes？ [数位DP]【动态规划】

2016-08-25 15:54:39 Tabris_ 阅读数：386

博客爬取于2020-06-14 22:43:41
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52315342

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1140
------------------------------------.
D - How Many Zeroes?
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu

Description
Jimmy writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will 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 and n, (m ≤ n).

Output
For each case, print the case number and the number of zeroes written down by Jimmy.

Sample Input
5
10 11
100 200
0 500
1234567890 2345678901
0 4294967295
Sample Output
Case 1: 1
Case 2: 22
Case 3: 92
Case 4: 987654304
Case 5: 3825876150

-----------------------------------------.
题目大意 ：就是求区间[m,n]之间的所有数中 0的个数是多少 ?

解题思路 ： 、
标准的数位DP
dp[位数][0~9][0的个数];
然后记忆化搜索的时候
dfs(第几位,前面有没有非0的数,取数的限制,0的个数);
大概这样就能AC了 然后注意下细节就好了…

附本题代码
----------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MOD  = 1000000007;
const int maxn = 200010;

int num[30];
LL dp[30][12][20];

LL dfs(int pos,int pre,int limit,int m)
{
    if(pos < 0) return m+(pre==0);

    if(dp[pos][pre][m]!=-1&&!limit&&pre)
        return dp[pos][pre][m];

    int endi = 9;
    if(limit) endi = num[pos];

    LL res = 0;
    for(int i=0;i<=endi;i++)
        res+=dfs(pos-1,i||pre,limit&&(i==endi),m+(pre&&i==0));

    if(!limit && pre) dp[pos][pre][m] = res;
    return res;
}

LL solve(LL n)
{

    int len = 0;

    if(n==0) num[len++] = 0;

    while(n)
    {
        num[len++] = n%10;
        n/=10;
    }

    return dfs(len-1,0,1,0);
}

int main()
{
	memset(dp,-1,sizeof(dp));
    int _,p=0;
    scanf("%d",&_);
    while(_--)
    {
        LL n,m;
        scanf("%lld%lld",&n,&m);
       // printf("%lld %lld\n",solve(m),solve(n-1));
        printf("Case %d: %lld\n",++p,solve(m)-solve(n-1));
    }

    return 0;
}