poj3252（数位dp）

素颜马尾好姑娘i 2021-12-21 01:03 304阅读 0赞

题目链接：https://vjudge.net/problem/POJ-3252

题意：求\[l,r\]之间的Round Number数，RN数即化为二进制后0的个数不少于1的个数的数。

思路：之前用组合数求写过，最近学数位dp，又用数位dp来写一次。用dp\[pos\]\[n0\]\[n1\]表示长为pos+1的数（我从0开始定义的），之前已经有n0个0和n1个1的前提下RN数有多少，用lead表示是否前导0，最后的递归终止条件为if(pos==-1) return n0>=n1。

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    
    int a[35],dp[35][35][35];
    
    int dfs(int pos,int n0,int n1,bool lead,bool limit){
        if(pos==-1) return n0>=n1;
        if(!limit&&!lead&&dp[pos][n0][n1]!=-1) return dp[pos][n0][n1];
        int up=limit?a[pos]:1,tmp=0;
        for(int i=0;i<=up;++i){
            if(lead){
                if(!i) tmp+=dfs(pos-1,n0,n1,lead&&!i,limit&&i==a[pos]);
                else tmp+=dfs(pos-1,n0,n1+1,lead&&!i,limit&&i==a[pos]);
            }
            else{
                if(!i) tmp+=dfs(pos-1,n0+1,n1,lead&&!i,limit&&i==a[pos]);
                else tmp+=dfs(pos-1,n0,n1+1,lead&&!i,limit&&i==a[pos]);
            }
        }
        if(!limit&&!lead) dp[pos][n0][n1]=tmp;
        return tmp;
    }
    
    int solve(int x){
        int pos=0;
        while(x){
            a[pos++]=x%2;
            x/=2;
        }
        return dfs(pos-1,0,0,true,true);
    }
    
    int main(){
        memset(dp,-1,sizeof(dp));
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d",solve(r)-solve(l-1));
        return 0;
    }

转载于:https://www.cnblogs.com/FrankChen831X/p/10763022.html

发表评论取消回复

表情：

评论列表（有 0 条评论，304人围观）

还没有评论，来说两句吧...

相关阅读

相关数位DP 详解

序 > 天堂在左，战士向右引言数位DP在竞赛中的出现几率极低，但是如果不会数位DP，一旦考到就只能暴力骗分。以下是数位DP详解，涉及到的例题有：

叁歲伎倆/ 2023年08月17日 17:38/ 0 赞/ 140 阅读

相关数位dp小结

数位dp小结关于limit的问题在数位dp中,limit的作用主要有两个。控制枚举的界限，倘若没有界限，每一位的枚举范围都是0-9. 但如果有界限，

桃扇骨/ 2023年07月03日 07:22/ 0 赞/ 20 阅读

相关 POJ 3252-Round Numbers【二进制数位DP】

题意：问你一个区间内有多少个二进制下0的个数比1的多的数。思路：dp\[i\]\[j\]\[k\] 表示第i位二进制长度为k，其中0的个数为j的答案，然后剩下的就是一些细节

桃扇骨/ 2023年06月01日 12:46/ 0 赞/ 4 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 226 阅读

相关 Bomb（数位Dp）

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Oth

布满荆棘的人生/ 2022年08月03日 00:09/ 0 赞/ 202 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 310 阅读

相关【数位DP】Round Numbers POJ - 3252

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

阳光穿透心脏的1/2处/ 2022年06月08日 14:08/ 0 赞/ 167 阅读

相关 poj3252（数位dp）

题目链接：https://vjudge.net/problem/POJ-3252 题意：求\[l,r\]之间的Round Number数，RN数即化为二进制后0的个数不少于1

素颜马尾好姑娘i/ 2021年12月21日 01:03/ 0 赞/ 305 阅读

相关 poj 3208 Apocalypse Someday（数位dp）

题意：给定n，输出第n大包含666的数字。分析：数位dp，详见《算法竞赛进阶指南》P342-344。代码： include<iostream>

客官°小女子只卖身不卖艺/ 2021年11月29日 06:36/ 0 赞/ 215 阅读

相关数位DP模板

int a[20]; ll dp[20][state]; ll dfs(int pos,/state变量/,bool lead/前导零/,bool li

左手的ㄟ右手/ 2021年09月19日 05:42/ 0 赞/ 371 阅读