hdu3652(数位dp模板)

#include<iostream>
#include<string.h>
#include<cmath>
#include<set>
#include<map>
#include<string>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
using namespace std;
typedef long long ll;
inline ll read() {
    ll sum = 0, f = 1;
    char p = getchar();
    for (; !isdigit(p); p = getchar()) if (p == ‘-‘)f = -1;
    for (; isdigit(p); p = getchar())  sum = sum * 10 + p - 48;
    return sum * f;
}
const int maxn = 50;
ll dp[maxn][10];
ll dig[maxn];
void init() {
    dp[0][0] = 1;
    for (int i = 1; i < maxn; 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];
            }
        }
    }
}
ll n, len,t;
ll solve(ll n) {
    len = 0;
    ll t = n;
    while (t) {
        dig[++len] = t % 10;
        t /= 10;
    }dig[len + 1] = 0;
    ll res = 0;
    for (int i = len; i >= 1; i--) {
        for (int j = 0; j < dig[i]; j++) {
            if (!(dig[i + 1] == 4 && j == 9))res += dp[i][j];
        }
        if (dig[i] == 9 && dig[i + 1] == 4) {//默认n是满足条件的(solve(n)+1),但是发现不满足,res--
            res--;
            break;}
    }
    return res;
}
int main() {
    //freopen("test.txt", "r", stdin);
    int T = read();
    init();
    while (T--) {
        n = read();
        printf("%lld\n",(n+1)-(solve(n)+1));//求包含49的那就减去不包含49的
        //init()求出的个数数是包含0的
    }
    return 0;
}