题目链接：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
     
      #include
      
       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;}