HDU 3555 Bomb(数位dp)

Description:

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the blast would add one point. Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Input:

The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description. The input terminates by end of file marker.

Output

For each test case, output an integer indicating the final points of the power.

Sample Input:

3
1
50
500

Sample Output:

0
1
15

Hint:

From 1 to 500, the numbers that include the sub-sequence “49” are “49”,“149”,“249”,“349”,“449”,“490”,“491”,“492”,“493”,“494”,“495”,“496”,“497”,“498”,“499”, so the answer is 15.

题目链接

之前写这种题(HDU 2089、2018年全国多校算法寒假训练营练习比赛（第二场）G)是直接对数据范围内所有数进行判断打表再在询问时循环计数，但是由于这题数据范围很大不能这么写，所以就学习了一下数位dp。

此题数位dp中dp[i][j]代表i位数中首位为j时不含49的数字个数。

那么状态转移公式就为 $d p [i] [j] = \sum_{k = 0}^{9} d p [i - 1] [k]$ ，其中j=4和k=9不能同时满足。

那么对于询问N，在计算1-N中不含49数字个数的时候从N的最高位Len开始求所有 $\sum_{j = 0}^{9} d p [L e n] [j]$ 之和并计入结果之中，依次向低位循环计数，当且仅当高一位数为4时dp[Len][9]不计数，当N的某两位为49时跳出循环(此时与低位数无关，无论低位数是几都会含有49)。

最后用总数减去计算得到的不含有49的数量即为含有49的数量。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e1 + 5;

long long Dp[maxn][maxn];

void Init() {
    memset(Dp, 0, sizeof(Dp));
    Dp[0][0] = 1;
    for (int i = 1; i <= 19; ++i) {
        for (int j = 0; j < 10; ++j) {
            for (int k = 0; k < 10; ++k) {
                if (!(j == 4 && k == 9)) {
                    Dp[i][j] += Dp[i - 1][k];
                }
            }
        }
    }
}

long long Cal(long long X) {
    long long Ans = 0, Len = 0;
    long long Digit[maxn];
    while (X) {
        Digit[++Len] = X % 10;
        X /= 10;
    }
    Digit[Len + 1] = 0;
    for (int i = Len; i > 0; --i) {
        for (int j = 0; j < Digit[i]; ++j) {
            if (Digit[i + 1] != 4 || j != 9) {
                Ans += Dp[i][j];
            }
        }
        if (Digit[i + 1] == 4 && Digit[i] == 9) {
            break;
        }
    }
    return Ans;
}

int main(int argc, char *argv[]) {
    Init();
    int T;
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        long long N;
        scanf("%lld", &N);
        printf("%lld\n", N + 1 - Cal(N + 1));
    }
    return 0;
}