JS's Blog
0%

Hdu 2089 - 不要62 （数位dp，暴力）

Posted on Edited on In ,

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

题目大意：
找出区间[n,m][n,m]内不含子串62以及4的数字个数

分析：
找不含4的数字直接在向下层dp时遇到i==4i==4的情况跳过即可，对于不含62的情况，加一个参数prepre，记录之前一个数位的情况，若之前为6，且当前要放2，则跳过，按模板dp即可

这题的数据量很小，所以直接暴力也可以，当然一般当做数位dp练手，上手可以先先试试不看模板，敲一发没有额外限制条件的dp，也就是求0−n0-n之间数字的个数，然后试着通过增加、修改条件，达成题目的要求

代码：

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
#include <cstdio>
#include <cstring>

typedef long long ll;

int dp[30][2];

int a[50],pos;

ll dfs(int pos,int pre,bool sta,bool limit)
{
    if (pos==-1)
        return 1;
    if (!limit&&dp[pos][sta]!=-1)   return dp[pos][sta];
    int up = limit?a[pos]:9;
    ll ans = 0;
    for (int i = 0 ; i <= up ; i ++)
    {
        if (pre==6&&i==2)
            continue;
        if (i==4)
            continue;
        ans += dfs(pos-1,i,i==6,limit&&i==pos[a]);
    }
    if (!limit) dp[pos][sta] = ans;
    return ans;
}


ll solve(ll n)
{
    pos = 0;
    while (n)
    {
        a[pos++] = n%10;
        n /= 10;
    }
    return dfs(pos-1,0,false,true);
}

int main()
{
    int n,m;
    memset(dp,-1,sizeof(dp));
    while (~scanf("%d%d",&n,&m)&&(n||m))
    {
        if (n>m)
        {
            n = n^m;
            m = n^m;
            n = n^m;
        }
        printf("%lld\n",solve(m)-solve(n-1));
    }
}