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

╰半橙微兮° 2022-06-08 09:59 148阅读 0赞

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

[vjudge题目链接][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;/*返回当前状态的解*/
    }

[vjudge]: https://vjudge.net/problem/HDU-2089