hdu 2089 不要62

Posted on | In | 阅读

数位dp，先预处理出所有i位数字的情况

dp[i][j]，i代表数字的位数，j代表状况
dp[i][0],表示不存在不吉利数字的个数
dp[i][1],表示不存在不吉利数字，且最高位为2的个数
dp[i][2],表示存在不吉利数字的个数

从数字的最高位开始，例如98765，从9这一位开始，不幸运的个数为ans。

这一位数字如果由0~8这九个数字打头之后都是有完整的i-1位数的，所以这一位只考虑填入0~8，然后这一位作为9的时候讨论下一位就行了。

  1. 加上之前就已经是不吉利的情况。直接ans+= 9*dp[i-1][2]

  2. 因为加上了这一位而变成不吉利的数的情况，一共分为三种情况。

    • 这位如果可以填入4，那么ans += dp[i-1][0]
    • 这位可以填入6，那么ans += dp[i-1][1]
    • 如果这一位可以填入2，并且前一位是6，那么ans += dp[i][1]

  3. 最后该位填入arr[i]，进入下一位开始讨论。

  4. 算出ans之后，n-ans就是前n个数字中吉利的数字，算区间的话用头尾减一下就好了。

C++ Code

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
#include <iostream>
#include <stdio.h>
#include <cstring>

using namespace std;
int dp[10][3];
//dp[i][j]，i代表数字的位数，j代表状况
//dp[i][0],表示不存在不吉利数字
//dp[i][1],表示不存在不吉利数字，且最高位为2
//dp[i][2],表示存在不吉利数字

void init()
{
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i <= 6; i++)//最大999999
    {
        //最高位加上不含4的9个数字的状况，但因为会放6，所以要减去前一种开头为2的情况
        dp[i][0] = 9 * dp[i-1][0] - dp[i-1][1];
        //只有2
        dp[i][1] = dp[i-1][0];
        //已经含有的前面放什么数都可以，或者是放一个4，或者是在2前面放6
        dp[i][2] = dp[i-1][0] + dp[i-1][1] + 10 * dp[i-1][2];
    }
}

int solve(int n)///1到n（不算n）幸运数个数
{
    int counts = 0, tmp = n, flag = 0, arr[10], ans = 0;//ans为不幸运数
    while(n)
    {
        arr[++counts] = n % 10;
        n /= 10;
    }
    arr[counts + 1] = 0;
	///每一步都只计算到0~arr[i]-1开头的情况，然后这一位作为arr[i]开始计算下一位
    for(int i = counts; i >=1; i--)
    {
        ///0~arr[i]-1打头有完整的i-1位数
        ans += dp[i-1][2] * arr[i];
		
		///因为加上该位才变成不吉利的情况
        if(flag)
			///高位已经出现4或62了，所有数都要算
            ans += dp[i-1][0] * arr[i];
        else
        {
            ///若该位大于4，就要加上4+ i-1位幸运数构成的不幸运数
            if(arr[i] > 4)
                ans += dp[i-1][0];
            if(arr[i+1] == 6 && arr[i] > 2)
                ans += dp[i][1];
            if(arr[i] > 6)
                ans += dp[i-1][1];
        }
        if(arr[i] == 4 || (arr[i+1] == 6 && arr[i] == 2))
            flag = 1;
    }
    return tmp - ans;
}

int main()
{
    int n, m;
    init();
    while(scanf("%d%d", &n, &m) && n+m)
    {
        printf("%d\n", solve(m + 1) - solve(n));
    }
    return 0;
}