【数位DP】F(x) HDU - 4734

川长思鸟来 2022-06-08 13:21 176阅读 0赞

Think:  
1知识点：数位DP  
2题意：输入A，B，询问在\[0, B\]区间内，F(xi) <= F(A)的数的数量，其中F(x)的定义为：F(x) = An \* 2^n-1 + An-1 \* 2^n-2 + … + A2 \* 2 + A1 \* 1，其中数字x的n个数位为 (AnAn-1An-2 … A2A1)  
3方法：分离B的数位作为约束条件，然后计算得到F(A)，进而从F(A)的最高位开始试探，每次减少(2^pos)，直到满足F(x) < F(A)，记录状态值，dp数组含义：dp\[i\]\[j\]表示i位数比j小的数的个数  
4反思：  
（1）：dfs中pos == -1的状态  
（2）：dfs中num < 0的状态

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int dp[24][5004], tp, link[24];
    
    int tri(int x);
    int dfs(int pos, int num, bool is_max);
    int solve(int A, int B);
    
    int main(){
        memset(dp, -1, sizeof(dp));
        int k = 1, T, A, B;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &A, &B);
            printf("Case #%d: %d\n", k++, solve(A, B));
        }
        return 0;
    }
    int tri(int x){
        int sum = 0, p = 1;
        while(x){
            sum += (x%10)*p;
            p *= 2;
            x /= 10;
        }
        return sum;
    }
    int solve(int A, int B){
        tp = 0;
        while(B){
            link[tp++] = B%10;
            B /= 10;
        }
        int num = tri(A);
        return dfs(tp-1, num, true);
    }
    int dfs(int pos, int num, bool is_max){
        if(pos == -1) return num >= 0;
        if(num < 0) return 0;/**/
        if(!is_max && ~dp[pos][num])
            return dp[pos][num];
        int cnt = 0, is_top = 9;
        if(is_max)
            is_top = link[pos];
        for(int i = 0; i <= is_top; i++){
            cnt += dfs(pos-1, num-i*(1<<pos), is_max && i == is_top);
        }
        if(!is_max)
            dp[pos][num] = cnt;
        return cnt;
    }

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