hdu5898_数位dp

http://acm.hdu.edu.cn/showproblem.php?pid=5898

Problem Description

For a number,if the length of continuous odd digits is even and the length of continuous even digits is odd,we call it odd-even number.Now we want to know the amount of odd-even number between L,R(1<=L<=R<= 9*10^18).

Input

First line a t,then t cases.every line contains two integers L and R.

Output

Print the output for each case on one line in the format as shown below.

Sample Input

2 1 100 110 220

Sample Output

Case #1: 29 Case #2: 36

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <ctime>
 8 #include <queue>
 9 #include <list>
10 #include <set>
11 #include <map>
12 using namespace std;
13 #define INF 0x3f3f3f3f
14 typedef long long LL;
15 
16 int bit[20];
17 LL dp[20][20][2];dp[len][sum][tag]//前len 位，到当前为为止有num 个tag, tag=0 表示偶数，1为奇数
18 LL dfs(int len, int zer, int num, int tag, int flag)
19 {
20     if(len < 1)
21         return (num + tag) % 2 || (zer==0);
22     if(flag && dp[len][num][tag] != -1)
23         return dp[len][num][tag];
24     int te = flag ? 9 : bit[len];
25     LL sum = 0;
26     for(int i = 0; i <= te; i++)
27     {
28         if(i % 2 == 0){
29             if(zer == 0 && i == 0)
30                 sum += dfs(len-1, 0, 0, 0, flag || i < te);
31             else if(tag == 0)
32                 sum += dfs(len-1, 1, num+1, tag, flag || i < te);
33             else if(tag == 1 && num % 2 == 0)
34                 sum += dfs(len-1, 1, 1, 0, flag || i < te);
35         }
36         if(i % 2 == 1){
37             if(tag == 1)
38                 sum += dfs(len-1, 1, num+1, tag, flag || i < te);
39             else if(zer==0 || (tag == 0 && num % 2 == 1))
40                 sum += dfs(len-1, 1, 1, 1, flag || i < te);
41         }
42     }
43     if(flag)
44         dp[len][num][tag] = sum;
45     return sum;
46 }
47 LL solve(LL n)
48 {
49     memset(bit, 0, sizeof(bit));
50     int len = 0;
51     while(n)
52     {
53         bit[++len] = n % 10;
54         n /= 10;
55     }
56     return dfs(len, 0, 0, 0, 0);
57 }
58 int main()
59 {
60     LL l, r;
61     int t;
62     scanf("%d", &t);
63     memset(dp, -1, sizeof(dp));
64     for(int ca = 1; ca <= t; ca++)
65     {
66         scanf("%lld%lld", &l, &r);
67         printf("Case #%d: %lld
", ca, solve(r)-solve(l-1));
68     }
69     return 0;
70 }