【数位DP】C~K的幸运数字

淡淡的烟草味﹌ 2022-06-08 09:06 175阅读 0赞

Think:  
1知识点：数位DP+记忆化搜索  
2思考：  
（1）：dp数组记录状态应记录\[数位\]\[是否已经含有47\]\[前一位数值\]  
（2）：dp数组初始化位置应在总的查询前(所有的dfs搜索之前)，进而通过记忆化搜索记录状态，优化时间复杂度  
（3）：记忆化搜索记录之前已经搜索得到的状态  
（4）：dfs初始传入的状态

[C~K的幸运数字——SDUT题目链接][C_K_SDUT]  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
据说，QAQ 的幸运数字是含有 “47” （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047 是他的幸运数字，而 74, 1234, 407 就不是他的幸运数字。  
而对 C~K 来说，只要不是 QAQ 的幸运数字的数都是他的幸运数字。那么他想问你，在闭区间 \[l, r\] 中，有多少个自己的幸运数字？

Input  
输入数据有多组。第 1 行输入 1 个整数 T (1 <= T <= 10000) 表示数据组数。  
对于每组数据，输入 1 行，包含 2 个整数 l, r (1 <= l <= r < 10^9)，表示 C~K 要询问的区间。

Output  
对于每组数据，在 1 行中输出 1 个整数，表示区间内 C~K 的幸运数字的个数。

Example Input  
3  
1 1  
10 50  
1 500

Example Output  
1  
40  
485

Hint

Author  
「山东理工大学第一届ACM知识挑战赛（机试）」bLue

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int dp[24][2][14], tp, link[24];
    
    int dfs(int pos, bool had_47, int pre, bool is_max);
    int solve(int x);
    
    int main(){
        memset(dp, -1, sizeof(dp));
        int T, l, r, ans;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &l, &r);
            ans = (r-l+1) - (solve(r)-solve(l-1));
            printf("%d\n", ans);
        }
        return 0;
    }
    int solve(int x){
        if(!x)
            return 0;
        tp = 0;
        while(x){
            link[tp++] = x%10;
            x /= 10;
        }
        return dfs(tp-1, false, -1, true);
    }
    int dfs(int pos, bool had_47, int pre, bool is_max){
        if(pos == -1)
            return had_47;
        if(!is_max && dp[pos][had_47][pre] != -1)
            return dp[pos][had_47][pre];
        int up_max = 9;
        if(is_max)
            up_max = link[pos];
        int cnt = 0;
        for(int i = 0; i <= up_max; i++){
            if(pre == 4 && i == 7)
                cnt += dfs(pos-1, true, i, is_max && i == link[pos]);
            else
                cnt += dfs(pos-1, had_47, i, is_max && i == link[pos]);
        }
        if(!is_max)
            dp[pos][had_47][pre] = cnt;
        return cnt;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 20ms
    Take Memory: 152KB
    Submit time: 2017-09-20 21:37:34
    ****************************************************/

[C_K_SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3904.html