JS's Blog
0%

Hdu 3555 - Bomb （数位dp）

Posted on Edited on In ,

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

题目大意：
给定一个NN，找出1−N1-N间含有子串49的数字个数

分析：
这个和不要62类似，但是略有不同，现在找的是含有49的数，所以一样记一个参数pre，代表前一个数位的值，然后记一个sta，这个和不要62中的sta有些不同，有三重状态

  • sta = 0前一个数位不是6
  • sta = 1前一个数位是6
  • sta = 2之前出现过49
    显然最后pos==−1pos==-1的时候，只有sta==2sta==2的结果才能返回1

另外对于当sta=2时，当前位无论如何放置都不会改变sta的值，而对于其他情况，类似不要62

分析：

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

using namespace std;
typedef long long ll;

ll dp[30][10];

int a[50],pos;

ll dfs(int pos,int pre,int sta,bool limit)
{
    if (pos==-1)
    {
        return sta==2;
    }

    if (!limit&&dp[pos][sta]!=-1)  {
        //printf("dp[%d][%d] = %lld\n",pos,sta,dp[pos][sta]);
        return dp[pos][sta];
    }
    int up = limit?a[pos]:9;
    ll ans = 0;
    for (int i = 0 ; i <= up ; i ++)
    {
        int temp = sta;
        if (pre==4&&i==9)
            temp = max(temp,2);
        else if (i==4)
            temp = max(temp,1);
        else
        {
            if (temp!=2)
                temp = 0;
        }
        ans += dfs(pos-1,i,temp,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,0,true);
}

int main()
{
    ll n;
    int T;
    scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    while (T--)
    {
        scanf("%lld",&n);
        printf("%lld\n",solve(n));
    }
}