【数位DP】B-number HDU - 3652

朱雀 2022-06-08 13:56 180阅读 0赞

Think:  
1知识点：数位DP  
2题意：输入r，判断\[1, r\]区间内有多少个“wqb-number”，“wqb-number”的定义为数位内含有13且可以被13整除，例如13,2613是“wqb-number”，而143和131不是“wqb-number”，143中1和3不是连续存在，131不能被13整除。  
3反思：  
（1）：dp数组的控制条件应与dfs中控制变量相对应  
（2）：dp\[pos\]\[is\_13\]\[num\]\[pre\];  
（3）：dfs(pos, is\_13, num, pre, is\_max);

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——dp数组的控制条件无is\_13

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    int dp[24][24][14], tp, link[24];
    
    int dfs(int pos, bool is_13, int num, int pre, bool is_max);
    int solve(int x);
    
    int main(){
        memset(dp, -1, sizeof(dp));
        int r;
        while(~scanf("%d", &r)){
            printf("%d\n", solve(r));
        }
        return 0;
    }
    int solve(int x){
        tp = 0;
        while(x){
            link[tp++] = x%10;
            x /= 10;
        }
        return dfs(tp-1, false, 0, -1, true);
    }
    int dfs(int pos, bool is_13, int num, int pre, bool is_max){
        if(pos == -1){
            return (is_13) && (!num);
        }
        if(!is_max && ~dp[pos][num][pre])
            return dp[pos][num][pre];
        int up_top = 9;
        if(is_max)
            up_top = link[pos];
        int cnt = 0;
        for(int i = 0; i <= up_top; i++){
            if(pre == 1 && i == 3)
                cnt += dfs(pos-1, true, (num*10+i)%13, i, is_max && i == up_top);
            else
                cnt += dfs(pos-1, is_13, (num*10+i)%13, i, is_max && i == up_top);
        }
        if(!is_max)
            dp[pos][num][pre] = cnt;
        return cnt;
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    int dp[24][2][24][14], tp, link[24];
    
    int dfs(int pos, bool is_13, int num, int pre, bool is_max);
    int solve(int x);
    
    int main(){
        memset(dp, -1, sizeof(dp));
        int r;
        while(~scanf("%d", &r)){
            printf("%d\n", solve(r));
        }
        return 0;
    }
    int solve(int x){
        tp = 0;
        while(x){
            link[tp++] = x%10;
            x /= 10;
        }
        return dfs(tp-1, false, 0, -1, true);
    }
    int dfs(int pos, bool is_13, int num, int pre, bool is_max){
        if(pos == -1){
            return (is_13) && (!num);
        }
        if(!is_max && ~dp[pos][is_13][num][pre])
            return dp[pos][is_13][num][pre];
        int up_top = 9;
        if(is_max)
            up_top = link[pos];
        int cnt = 0;
        for(int i = 0; i <= up_top; i++){
            if(pre == 1 && i == 3)
                cnt += dfs(pos-1, true, (num*10+i)%13, i, is_max && i == up_top);
            else
                cnt += dfs(pos-1, is_13, (num*10+i)%13, i, is_max && i == up_top);
        }
        if(!is_max)
            dp[pos][is_13][num][pre] = cnt;
        return cnt;
    }

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