本文共 1426 字，大约阅读时间需要 4 分钟。

数位dp

POJ 3252 Round Numbers

由于一个二进制数的最高位一定为1，所以需要用first标记最高位是否是1。如果是的话，那么这一位随便放。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int dp[50][50][50], bit[50];//dp[len][num0][num1]//flag表示最高位是否有限制，1表示有限制 //first表示第一个1是否放下，1表示没放下 int dfs(int highBit, int num0, int num1, int flag, int first){   	if (highBit==0)			return num0>=num1;	if (flag==0 && first==0 && dp[highBit][num0][num1]!=-1)			return dp[highBit][num0][num1];	int ans=0;	int end=flag?bit[highBit]:1;		for (int digit=0; digit<=end; digit++){   		if (first){   			if (digit==0)				ans+=dfs(highBit-1, 0, 0, flag&&digit==end, 1);			else				ans+=dfs(highBit-1, num0, num1+1, flag&&digit==end, 0);			}else{   			if (digit==0)				ans+=dfs(highBit-1, num0+1, num1, flag&&digit==end, 0);			else				ans+=dfs(highBit-1, num0, num1+1, flag&&digit==end, 0);		}	}	if (flag==0 && first==0)		dp[highBit][num0][num1]=ans;	//记忆化 	return ans;}int solve(int n){   	//求出从0到n所有满足条件的数的个数 	int len=0;	while (n){   		bit[++len]=n&1;	//转成二进制 		n>>=1;	}	int ans=dfs(len, 0, 0, 1, 1);	//最开始最高位有限制，1没放下 	return ans;}int main(){   	memset(dp, -1, sizeof(dp));	int l, r;	while (scanf("%d%d", &l, &r)!=EOF){   		printf("%d\n", solve(r)-solve(l-1));	}	return 0;}