【数位DP】Round Numbers POJ - 3252

阳光穿透心脏的1/2处 2022-06-08 14:08 166阅读 0赞

Think:  
1知识点：数位DP+二进制  
2题意：输入一个区间判断有多少个“Round Number”，“Round Number”的定义为其二进制表示中0的数量大于等于1的数量

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int dp[40][40][40], tp, link[40];
    
    int dfs(int pos, int cnt0, int cnt1, bool lead, bool is_max);
    int solve(int x);
    
    int main(){
        memset(dp, -1, sizeof(dp));
        int l, r;
        while(~scanf("%d %d", &l, &r)){
            printf("%d\n", solve(r)-solve(l-1));
        }
        return 0;
    }
    int solve(int x){
        tp = 0;
        while(x){
            link[tp++] = x%2;
            x >>= 1;
        }
        return dfs(tp-1, 0, 0, true, true);
    }
    int dfs(int pos, int cnt0, int cnt1, bool lead, bool is_max){
        if(pos == -1)
            return cnt0 >= cnt1 && !lead;
        if(!is_max && !lead && ~dp[pos][cnt0][cnt1])
            return dp[pos][cnt0][cnt1];
        int up_top = 1;
        if(is_max)
            up_top = link[pos];
        int sum = 0;
        for(int i = 0; i <= up_top; i++){
            if(lead){
                if(i == 0){
                    sum += dfs(pos-1, 0, 0, true, false);
                }
                else if(i == 1){
                    sum += dfs(pos-1, 0, 1, false, is_max && i == up_top);
                }
            }
            else {
                if(i == 0){
                    sum += dfs(pos-1, cnt0+1, cnt1, false, is_max && i == up_top);
                }
                else if(i == 1){
                    sum += dfs(pos-1, cnt0, cnt1+1, false, is_max && i == up_top);
                }
            }
        }
        if(!is_max)
            dp[pos][cnt0][cnt1] = sum;
        return sum;
    }

[vjudge]: https://vjudge.net/problem/POJ-3252