航电提高课（数位DP）2021.07.09

这一类问题一般是与数位有关的区间统计问题，需要在数位上进行地推等操作。
例1、求1到N中有多少个数字包含49。
用记忆化DFS实现数位DP板子

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x;
ll a[100];
ll dp[100][2];//dp[pos][std]的状态表示第POS位在 状态下满足条件的元素个数，STA前一位的状态，这里表示前一位是不是4(重点：记录的时不受限情况下元素的个数） 
ll ans=0;
ll len;
//求A数组 
void work(int x){
    len=0;
    while(x!=0){
        a[++len]=x%10;
        x=x/10;
    }
    return ;
}
//数位DP，DFS记忆化搜搜 
ll dfs(ll n,bool is4,bool is_max){//is4表示前一位的状态，is_max表示前一位有没有到达上界限 
    if(!n) return 1;//n=0时表示已经搜索完一个数了，那么返回1 
    if(!is_max&&dp[n][is4]!=-1) return dp[n][is4];//前一位没有 到达上界限，且dp[][]之前已经求过了就可以直接返回了 
    ll anss=0; 
    ll m=is_max?a[n]:9;//如果前一位已经到达上界，那么下一位只能取0~a[n]的数，否则可以取1~9的数。 
    for(int i=0;i<=m;i++){
        if(is4&&i==9){//满足49的条件直接跳过 
            continue;
        }
        anss+=dfs(n-1,i==4,is_max&&i==m);//dfs下一层， is_max&&i==m一定要带上is_max,因为前面也必须时上界，整体才是上界，如N=1234，这里1034依然不是上界 
    }
    if(!is_max) dp[n][is4]=anss;//如果不受限制，就将结果存入d[][]中 
    return anss;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        memset(dp,-1,sizeof(dp));
        memset(a,0,sizeof(a));
        cin>>x;
        work(x);
        ans=dfs(len,false,true);//返回的ans值表示0~N中不含49的数的个数 
        cout<<x-(ans-1)<<endl;//不要忘记减去0 
    }
    return 0;
} 

练习题目
HDU2089 不要62
题解