[原创]HDU 5898&&2016 ACM/ICPC Asia Regional Shenyang Online/ odd-even number [数位DP]【动态规划】

2016-09-18 22:01:52 Tabris_ 阅读数：316

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

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

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5898

-----------------------------------------------------------.
odd-even number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 125 Accepted Submission(s): 66

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

Source
2016 ACM/ICPC Asia Regional Shenyang Online

--------------------------------------.
题目大意：
就是统计区间内满足连续奇数个数为偶数且连续偶数为奇数的数的个数

解题思路 ：
很明显一道数位DP
鄙人用的是记忆化搜索

开了4维数组
LL dp[30][3][30][3];
分别是位数 奇偶 正在判断的连续奇偶的长度 满不满足的状态

LL dfs(int pos,int pre,int x,int limit,int status,int lengh)
分别是位数/上一位的数字/上一位数字的奇偶性/数位的限制/满不满足的状态/正在判断的连续奇偶的长度

然后转移的时候注意的就是前导0的情况不要当成偶的数字给统计了 否则数会多

数位DP无非就三点
数组怎么开
记忆化搜索的参数
转移的过程
↑上面3点都解决了 相信数位DP的题目就解决了。

平时为了验证数位DP的正确性 在小数据的时候把记忆化注释掉了 交题的时候没改回来 就这样TLE了一发。。。GG
但也终于在比赛中AC了一道数位DP 也算是小进步

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

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <set>
# include <map>
# include <string>
# include <math.h>
# include <stdlib.h>
# include <time.h>
using namespace std;
typedef long long int LL ;
# define INF 0x3f3f3f3f
# define pb push_back
# define abs(a) (a)>0?(a):-(a)
# define lalal puts("*******");
/*************************************/

int num[30],len;
LL dp[30][3][30][3];
//weishu jiou changdu zhuangtai
LL dfs(int pos,int pre,int x,int limit,int status,int lengh)
{
    if(pos<0)  return status&&(lengh+x)%2==1;

    if(dp[pos][x][lengh][status]!=-1&&!limit)
        return dp[pos][x][lengh][status];

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

    LL res = 0;
    for(int i=0; i<=endi; i++)
    {
        if(pre==0&&i==0)//qiandao00
        {
            res+=dfs(pos-1,0,0,0,1,0);
        }
        else
        {
            if(pre==0)
            {
                res+=dfs(pos-1,1,i%2,limit&&(i==endi),1,1);

            }
            else
            {
                res+=dfs(pos-1,1,i%2,limit&&(i==endi),(i%2==x)?status:((lengh+x)%2==1)&&status,(i%2==x)?(lengh+1):(1));

            }
        }
    }
    if(!limit) dp[pos][x][lengh][status] =  res;
    return  res;
}
LL solve(LL n)
{
    if(n<=0) return 0;

    len = 0;
    while(n)
    {
        num[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,0,0,1,1,0);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    int _,p;
    scanf("%d",&_);

    p=0;
    while(_--)
    {
        LL l,r;
        scanf("%I64d%I64d",&l,&r);
        printf("Case #%d: %I64d\n",++p,solve(r)-solve(l-1));
    }

    return 0;
}