给出n，问所有[0,n]区间内的数中，不含有49的数的个数

 

数位dp，记忆化搜索

 

dfs(int pos,bool pre,bool flag,bool e)

pos:当前要枚举的位置

pre:当前要枚举的位置的前面是否为4

flag：枚举当前时，这个数的49时候被算过了

e:当前位置是否可以随便取值

 

dp[pos][pre][flag]

 

#include
     
      #include
      
       #include
       
        #include
        
         #define ull unsigned long longusing namespace std;const int maxn=66;ull dp[maxn][2][2];int a[maxn];ull solve(ull );int main(){    memset(dp,-1,sizeof dp);  //先初始化    int test;    cin>>test;    while(test--){        ull n;        cin>>n;        cout<
         
          <