HDU3555

题意：给定数字N，求1~N，有多少个数含49

数位dp+dfs，详见注释

AC代码

#include<iostream>
using namespace std;
typedef long long ll;int digit[20];
ll dp[20][2];
ll dfs(int len, bool if4, bool limit)//if4表示长为len上一位是否是4，limit表示最高位是否是上界（还是随机0~9）
{
    if (len == 0) return 1;if (!limit && dp[len][if4]) return dp[len][if4];//如果已经赋过值，直接returnll cnt = 0, up_bound = (limit ? digit[len] : 9);//定义上界，如果前面位都是上界，则该位也有上界为digitfor (int i = 0; i <= up_bound; i++){
    if (if4 && i == 9)//出现49不作任何操作continue;cnt += dfs(len - 1, i == 4, limit && i == up_bound);}if (!limit)dp[len][if4] = cnt;//不要忘记记忆化存储return cnt;
}
ll solve(ll num)
{
    int k = 0;while (num){
    digit[++k] = num % 10;//digit从1开始，存储低位到高位num /= 10;}return dfs(k, false, true);
}
int main()
{
    int T;cin >> T;while (T--){
    ll N;cin >> N;cout << N + 1 - solve(N) << endl;}
}