【数位DP+记忆化搜索】不要62 HDU - 2089

Think:
1知识点：数位DP+记忆化搜索
2思考：
（1）：注意符合题意条件的判断（当ok为true的状态）
3题意：输入一个区间，判断这个区间内不含4且不含62的数的数量

vjudge题目链接

以下为Accetped代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int dig[24];/*分离数位*/
LL dp[24][2][14];

LL dfs(int pos/*当前数位*/, bool state/*状态是否满足*/, int pre/*前一位的值*/, bool is_max/*是否达到临界*/);
LL solve(LL n);/*求解区间[1, n]*/

int main(){
memset(dp, -1, sizeof(dp));
int T;
    LL n;
scanf("%d", &T);
while(T--){
scanf("%lld", &n);
printf("%lld\n", solve(n));
    }
return 0;
}
LL solve(LL x){
memset(dig, 0, sizeof(dig));
int pos = 0;
while(x){
        dig[pos++] = x%10;
        x /= 10;
    }
return dfs(pos-1, 0, -1, 1);
}
LL dfs(int pos, bool state, int pre, bool is_max){
if(pos == -1)
return state;/*返回true表示当前状态满足条件进而累加，返回false表示当前状态不满足条件*/
if(!is_max && dp[pos][state][pre] != -1)
return dp[pos][state][pre];
int up_top = 9;
if(is_max)/*临界判断*/
        up_top = dig[pos];
    LL cnt = 0;
for(int i = 0; i <= up_top; i++){
if(pre == 4 && i == 9)/*条件满足*/
            cnt += dfs(pos-1, true, i, is_max && i == up_top);
else
            cnt += dfs(pos-1, state, i, is_max && i == up_top);
    }
if(!is_max)/*全局记忆化搜索:判断是否可记忆*/
        dp[pos][state][pre] = cnt;
return cnt;/*返回当前状态的解*/
}